Pagini recente » Cod sursa (job #791257) | Cod sursa (job #1779720) | Cod sursa (job #235665) | Cod sursa (job #3267517) | Cod sursa (job #1412196)
#include<bits/stdc++.h>
#define Nmax 2000003
using namespace std;
char A[Nmax], B[Nmax];
int pi[Nmax], DIM, V[Nmax], N;
void Write()
{
freopen("strmatch.out", "w", stdout);
printf("%d\n", DIM);
for(int i = 1; i <= min(DIM, 1000); ++ i)
printf("%d ", V[i]);
}
void prefix()
{
int k = 0, i;
for(i = 1; A[i]; ++ i) {
while(k && A[k] != A[i])
k = pi[k - 1];
if(A[k] == A[i])
++ k;
pi[i] = k;
}
N = i;
}
void Do_KMP()
{
int k = 0;
for(int i = 0; B[i]; ++ i) {
while(k && A[k] != B[i])
k = pi[k - 1];
if(A[k] == B[i])
++ k;
if(k == N)
V[++ DIM] = i - N + 1;
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
gets(A);
gets(B);
prefix();
Do_KMP();
Write();
return 0;
}