[BOJ] 18269 Where Am I?

문제

18269번: Where Am I?

Farmer John has gone out for a walk down the road and thinks he may now be lost!

https://www.acmicpc.net/problem/18269

풀이

코드

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
 
int n;
string s;
string tmp;
 
int chk() {
    string k = tmp;
    set<string> st;
    st.insert(k);
    for(int i = tmp.size(); i < n; i++) {
        k += s[i];
        k = k.substr(1);
        if (st.find(k) != st.end()) {
            st.clear(); return 0;
        }
        st.insert(k);
    }
    st.clear();
    return 1;
}
 
int main() {
    scanf("%d", &n);
    cin >> s;
    tmp = s;
    for(int i = 0; i < n; i++) {
        if (!chk()) {
            printf("%d", tmp.size()+1);
            return 0;
        }
        tmp.pop_back();
    }
    printf("1");
}