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
|
char s1[1000010], s2[1000010]; int nxt[1000010], l1, l2;
void () { nxt[1] = 0; int j = 0; for (int i = 1; i < l2; ++i) { while (j > 0 && s2[j + 1] != s2[i + 1]) j = nxt[j]; if (s2[j + 1] == s2[i + 1]) j++; nxt[i + 1] = j; } }
void kmp() { int j = 0; for (int i = 0; i < l1; ++i) { while (j > 0 && s2[j + 1] != s1[i + 1]) j = nxt[j]; if (s2[j + 1] == s1[i + 1]) j++; if (j == l2) { printf("%dn", i - l2 + 2); j = nxt[j]; } } }
int main() { cin >> s1 + 1; cin >> s2 + 1; l1 = strlen(s1 + 1); l2 = strlen(s2 + 1); pre(); kmp(); return 0; }
|
近期评论