Pagini recente » Cod sursa (job #59081) | Cod sursa (job #816017) | Cod sursa (job #3127154) | Cod sursa (job #2165143) | Cod sursa (job #186553)
Cod sursa(job #186553)
using namespace std;
#include <cstdio>
#include <cstring>
#define Lmax 2000000
int nr,L1,L2;
char A[Lmax],B[Lmax];
int T[Lmax];
int P[1000];
void buildT()
{
int i,k;
T[0]=-1;
k=-1;
for (i=1; i<L1; ++i)
{
while (A[k+1] != A[i] && k>=0)
k=T[k];
if (A[k+1] == A[i]) ++k;
T[i]=k;
}
}
void kmp()
{
int i,k;
k=-1;
for (i=0; i<L2; ++i)
{
while (A[k+1] != B[i] && k>=0)
k=T[k];
if (A[k+1] == B[i]) ++k;
if (k==L1-1)
P[nr++]=i-L1+1;
}
}
int main()
{
int i;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n",&A);
scanf("%s\n",&B);
L1=strlen(A);
L2=strlen(B);
buildT();
kmp();
printf("%d\n",nr);
for (i=0; i<nr && i<1000; ++i)
printf("%d ",P[i]);
fclose(stdout);
return 0;
}