문자열이 주어졌을 때
특정 문자열 a의 n번 반복으로 이루어져 있다고 생각할 수 있다.
이 때 n의 최대값을 구한다.
KMP의 P배열은 x위치에서 다른글자가 나왔을 때 P[x]위치부터 확인하면 된다는 것을 의미한다
만약 문자열 맨 끝에서 P배열을 쭉 따라갔을 때 항상 일정한 간격으로 점프한다면 해당 문자열은 점프한 간격만큼의 문자열로 반복되는 것이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | #include <stdio.h> #define mv 1000002 char p[mv]; int f[mv], m; int strlen(char *c) { int i = 0; while (c[i]) i++; return i; } int main() { while (1) { fgets(p, mv, stdin); if (p[0] == '.') break; m = strlen(p); if (p[m - 1] == '\n') p[--m] = 0; for (int i = 1, j = 0; i < m; i++) { while (j && p[i] != p[j]) j = f[j - 1]; if (p[i] == p[j]) f[i] = ++j; } int l = m - f[m - 1]; int temp = f[m - 1]; while (temp - f[temp - 1] == l) { temp = f[temp- 1]; } printf("%d\n", temp == 0 ? m / l : 1); for (int i = 0; i < m; i++) f[i] = 0; } return 0; } | cs |
'BOJ' 카테고리의 다른 글
| 10573 증가하는 수 (0) | 2018.02.18 |
|---|---|
| 11585 속타는 저녁 메뉴 (0) | 2018.02.18 |
| 1305 광고 (0) | 2018.02.18 |
| 1786 찾기 (0) | 2018.02.18 |
| 5670 휴대폰 자판 (0) | 2018.02.18 |