Pagini recente » Cod sursa (job #391382) | Cod sursa (job #205538) | Cod sursa (job #2447717) | Cod sursa (job #2812219) | Cod sursa (job #2416217)
#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[smax];
int lsp[nmax];
void preprocess_pattern(char *pattern, int lenght) {
int prefix_len = 0;
lsp[0] = 0;
int i = 1;
while (i < lenght) {
if (pattern[i] == pattern[prefix_len]) {
lsp[i] = ++prefix_len;
i++;
} else {
if (prefix_len == 0) {
lsp[i] = 0;
i++;
} else {
prefix_len = lsp[prefix_len - 1];
}
}
}
/*for (int i = 0; i < lenght; i++) {
cout << lsp[i]<<" ";
}cout<<endl;*/
}
void kmp_query(char *pattern, char *text) {
int pattern_len = strlen(pattern);
int text_len = strlen(text);
preprocess_pattern(pattern, pattern_len);
int i = 0, j = 0;
while (i < text_len) {
if (text[i] == pattern[j]) {
i++;
j++;
}
if (j == pattern_len) {
if (sol_cnt <= 1000) {
sol[sol_cnt++] = i - j;
j = lsp[j - 1];
} else {
return ;
}
}
if (i < text_len && text[i] != pattern[j]) {
if (j == 0) {
i++;
} else {
j = lsp[j - 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 < sol_cnt; i++) {
printf("%d ", sol[i]);
}
printf("\n");
return 0;
}