문자열 문제인데 KMP로 풀었다.
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 33 34 35 36 37 38 39 40 41 | #include <stdio.h> #include <iostream> #define mv 1000002 char t[mv], p[mv]; int f[mv], l, m, q[mv], qi; int strlen(char *s) { int i; for (i = 0; s[i]; i++); return i; } int main() { fgets(t, mv, stdin); fgets(p, mv, stdin); l = strlen(t); m = strlen(p); if (t[l - 1] == '\n') t[--l] = 0; 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; } for (int i = 0, j = 0; i < l; i++) { while (j && t[i] != p[j]) j = f[j - 1]; if (t[i] == p[j]) { if (j == m - 1) { q[qi++] = i - m + 2; j = f[j]; } else j++; } } printf("%d\n", qi); for (int i = 0; i < qi; i++) printf("%d\n", q[i]); return 0; } | cs |
'BOJ' 카테고리의 다른 글
4354 문자열 제곱 (0) | 2018.02.18 |
---|---|
1305 광고 (0) | 2018.02.18 |
5670 휴대폰 자판 (0) | 2018.02.18 |
5052 전화번호 목록 (0) | 2018.02.18 |
1072 게임 (0) | 2018.02.18 |