Pagini recente » Cod sursa (job #2256794) | Cod sursa (job #3290788) | Cod sursa (job #1868875) | Cod sursa (job #112440) | Cod sursa (job #2093059)
#include <stdio.h>
#include <cstring>
using namespace std;
FILE *f,*g;
char x[2000002],y[2000002],t[2000002];
int d[20000002],n,m,ss,v[1004],pi[2000002];
void citire()
{
fscanf(f,"%s",&t);
strcpy(x+1,t);
fscanf(f,"%s",&t);
strcpy(y+1,t);
m=strlen(x+1);
n=strlen(y+1);
}
void kmp()
{
int k=0,i;
for(i=2;i<=m;i++)
{
while(k && x[k+1]!=x[i])
k=pi[k];
if(x[k+1]==x[i])
k++;
pi[i]=k;
}
}
void kmp1()
{
int i,k=0;
for(i=1;i<=n;i++)
{
while(k && x[k+1]!=y[i])
k=pi[k];
if(y[i]==x[k+1])
k++;
d[i]=k;
if(d[i]==m&&ss<=1000) v[++ss]=i;
}
}
void afisare()
{
int i;
/*for(i=1;i<=m;i++)
fprintf(g,"%d ",pi[i]);
fprintf(g,"\n");
for(i=1;i<=n;i++)
fprintf(g,"%d ",d[i]);
fprintf(g,"\n");*/
fprintf(g,"%d\n",ss);
for(i=1;i<=ss;i++)
fprintf(g,"%d ",v[i]-m);
}
int main()
{
f=fopen("strmatch.in","r");
g=fopen("strmatch.out","w");
citire();
kmp();
kmp1();
afisare();
fclose(f);
fclose(g);
return 0;
}