Pagini recente » Cod sursa (job #1226697) | Cod sursa (job #1578888) | Cod sursa (job #535396) | Cod sursa (job #53303) | Cod sursa (job #267694)
Cod sursa(job #267694)
#include<stdio.h>
#include<string.h>
#define Nmax 2000002
FILE*f=fopen("strmatch.in","r");
FILE*g=fopen("strmatch.out","w");
char A[Nmax], B[Nmax];
int n, m;
int pi[Nmax];
void read()
{
fscanf(f,"%s\n%s",A,B);
n=strlen(A);
m=strlen(B);
int i;
for(i=n;i>0;--i) A[i] = A[i-1]; A[0]=' ';
for(i=m;i>0;--i) B[i] = B[i-1]; B[0]=' ';
}
void prefix()
{
pi[1]=0;
int i,k;
k=0;
for(i=2;i<=n;++i)
{
while(k>0 && A[k+1] != A[i]) k=pi[k];
if(A[k+1] == A[i]) k++;
pi[i] = k;
}
}
int s[1024];
void kmp()
{
int sol=0,i,q=0;
for(i=1;i<=m;++i)
{
while(q && A[q+1] != B[i]) q=pi[q];
if(A[q+1] == B[i]) ++q;
if(q==n)
{
++sol;
if(sol<=1000) s[sol] = i-n;
q=pi[n];
}
}
fprintf(g,"%d\n",sol);
if(sol>1000) sol=1000;
for(i=1;i<=sol;++i) fprintf(g,"%d ",s[i]);
}
int main()
{
read();
prefix();
kmp();
return 0;
}