Pagini recente » Cod sursa (job #2653739) | Cod sursa (job #2546622) | Cod sursa (job #2165488) | Cod sursa (job #525668) | Cod sursa (job #632881)
Cod sursa(job #632881)
#include<cstdio>
#include<string.h>
#define N 2000005
char A[N];
char B[N];
int pi[N];
int NA, NB;
int contor;
int arr[1005];
void Prefix(char* a) {
int j = 0;
pi[0] = 0;
for(int i = 1; i < NA; i++) {
while((a[j] != a[i]) && (j != 0)) {
j = pi[j-1];
}
if (a[j] == a[i])
pi[i] = ++j;
}
return;
}
void kmp() {
int j = 0;
for(int i = 0; i < NB; i++) {
while((B[i] != A[j]) && (j != 0)) {
j = pi[j-1];
}
if (B[i] == A[j])
if(j == NA - 1) {
contor++;
j = pi[j];
if (contor <= 1000) {
arr[contor] = i - NA + 1;
}
}
else
j++;
}
}
int min(int a, int b) {
if (a < b) return a;
return b;
}
int main() {
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",&A, &B);
NA = strlen(A);
NB = strlen(B);
Prefix(A);
kmp();
printf("%d\n",contor);
for(int i = 1; i <= min(contor, 1000); i++)
printf("%d ",arr[i]);
return 0;
}