Pagini recente » Cod sursa (job #620546) | Cod sursa (job #1472302) | Cod sursa (job #123433) | Cod sursa (job #2188643) | Cod sursa (job #516840)
Cod sursa(job #516840)
#include<stdio.h>
#include<string>
using namespace std;
#define niur 2000005
FILE *in=fopen("strmatch.in","r"),*out=fopen("strmatch.out","w");
char A[niur],B[niur];
int V[niur],la,lb,countt,AFI[1005];
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;
if(countt<1001) 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;
}