Pagini recente » Cod sursa (job #695970) | Cod sursa (job #471355) | Cod sursa (job #1377747) | Cod sursa (job #1109375) | Cod sursa (job #516835)
Cod sursa(job #516835)
#include<stdio.h>
#include<string>
using namespace std;
#define niur 2000000
FILE *in=fopen("strmatch.in","r"),*out=fopen("strmatch.out","w");
char A[niur],B[niur];
int V[niur],la,lb,countt,AFI[1001];
void pre()
{
int i,k=0;
la=strlen(A);
for(i=2;i<la;++i)
{
while(k&&A[i]!=A[k+1])
k=V[k];
if(A[k+1]==A[i])
++k;
V[i]=k;
}
}
void kmp()
{
int i,k=0;
lb=strlen(B);
for(i=1;i<lb;++i)
{
while(k&&A[k+1]!=B[i])
k=V[k];
if(A[k+1]==B[i])
++k;
if(k==la-1&&countt<1000)
AFI[++countt]=i-la+1;
}
}
int main()
{
int i;
A[0]=B[0]=2;
fscanf(in,"%s",&A[1]);
fscanf(in,"%s",&B[1]);
pre();
kmp();
fprintf(out,"%d\n",countt);
for(i=1;i<=countt;++i)
fprintf(out,"%d ",AFI[i]);
return 0;
}