실패함수에서 f[s.length-1]은 가장 긴 접두사이면서 접미사의 길이이다. 우리가 구하는 n은 s.length/(s.length-f[s.length-1])이다. 이 때 ABCAB같은 반례가 있기 때문에 나누어 떨어지는 경우에만 n으로 채택하도록 하자.
#include <bits/stdc++.h>
using namespace std;
constexpr int MAX = 1e6+10;
int fail[MAX];
void make_fail(string& s) {
int begin = 1, match = 0;
while (begin + match < s.length()) {
if (s[begin+match] == s[match]) {
match++;
fail[begin+match-1] = match;
}
else {
if (!match) begin++;
else {
begin += match - fail[match-1];
match = fail[match-1];
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
while (1) {
string s;
cin >> s;
if (s == ".") break;
memset(fail, 0, sizeof(fail));
make_fail(s);
if (s.length()%(s.length()-fail[s.length()-1])) cout << 1 << '\n';
else cout << s.length()/(s.length()-fail[s.length()-1]) << '\n';
}
return 0;
}
KMP 넘 어렵다.. 아직도 이해가 잘 안된다.
많이 풀어봐야겠다.