Pagini recente » Cod sursa (job #2592231) | Cod sursa (job #11463) | Cod sursa (job #1886367) | Cod sursa (job #2550874) | Cod sursa (job #2416252)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef signed long long ll;
typedef unsigned int uint;
typedef unsigned short ushort;
typedef unsigned char uchar;
const int nmax = 2000001;
const int smax = 2001;
char A[nmax];
char B[nmax];
int sol_cnt;
int sol[nmax];
int lsp[nmax];
void kmp_query(char *pattern, char *text) {
int pattern_len = strlen(pattern);
int text_len = strlen(text);
for (int i = 1, k = 0; i < pattern_len; i++) {
while (k && pattern[k] != pattern[i]) k = lsp[k - 1];
if (pattern[k] == pattern[i]) k++;
lsp[i] = k;
}
for (int i = 0, k = 0; i < text_len; i++) {
while (k && pattern[k] != text[i]) k = lsp[k - 1];
if (pattern[k] == text[i]) ++k;
if (k == pattern_len) {
sol[sol_cnt++] = i - k + 1;
}
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s", A);
scanf("%s", B);
kmp_query(A, B);
printf("%d\n", sol_cnt);
for (int i = 0; i < min(sol_cnt, 1000); i++) {
printf("%d ", sol[i]);
}
printf("\n");
return 0;
}