Pagini recente » Cod sursa (job #51639) | Cod sursa (job #1637168) | Cod sursa (job #3150146) | Cod sursa (job #1728983) | Cod sursa (job #1133084)
#include <iostream>
#include<stdio.h>
#include<cstdlib>
#include<string.h>
using namespace std;
FILE *f,*g;
int n,m,i,j,first,curr,val[2000000],l;
char a[2000000],b[2000000];
int kmp[2000000];
int main()
{
f=fopen("strmatch.in","r");
g=fopen("strmatch.out","w");
fscanf(f,"%s%s",&a,&b);
n=strlen(a);
m=strlen(b);
kmp[0]=1;
if (n==1)
{
for(i=0;i<=m-1;i++)
{
if (a[0]==b[i])
{
l++;
val[l]=i;
if (l==1000)
{
fprintf(g,"%d\n",l);
for(i=1;i<=l;i++) fprintf(g,"%d ",val[i]);
return 0;
}
}
}
fprintf(g,"%d\n",l);
for(i=1;i<=l;i++) fprintf(g,"%d ",val[i]);
return 0;
}
for(i=1;i<=n-1;i++)
{
j=kmp[i-1];
while(j<i&&a[i]!=a[i-j])
j+=kmp[i-1-j];
if (j==i) {if (a[i]==a[0]) kmp[i]=i; else kmp[i]=i+1;}
else kmp[i]=j;
}
if (a[0]==b[0]) {first=0;}
else {first=1;}
for(i=1;i<=m-1;i++)
{
while(first<i&&b[i]!=a[i-first]) first+=kmp[i-1-first];
if (first==i) {if (b[i]==a[0]) first=i; else first=i+1;}
if (i-first==n)
{l++;val[l]=l;
if (l==1000) {fprintf(g,"%d\n",l);
for(i=1;i<=l;i++) fprintf(g,"%d ",val[i]);
return 0;}
first+=kmp[n-1];
}
}
fprintf(g,"%d\n",l);
for(i=1;i<=l;i++) fprintf(g,"%d ",val[i]);
return 0;
}