Pagini recente » Cod sursa (job #1893509) | Cod sursa (job #2319383) | Cod sursa (job #434654) | Cod sursa (job #2870256) | Cod sursa (job #1132381)
#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]=0;
for(i=1;i<=n-1;i++)
{
j=kmp[i-1];
while(j&&a[i]!=a[i-j]) j=kmp[i-j];
if (j==0) {if (a[i]==a[0]) kmp[i]=i; else kmp[i]=0;}
else kmp[i]=j;
}
if (a[0]==b[0]) {first=0;}
else {first=-1;}
for(i=1;i<=m;i++)
{
if (first==-1)
{
if (a[0]==b[i]) {first=i;}
}
else
{
if (a[i-first]==b[i])
{
if (i-first==n-1)
{
l++;
val[l]=first;
if (l==1000) break;
if (kmp[n-1]==0) {first=-1;}
else {first+=kmp[n-1];}
}
}
else
{
while(kmp[i-1-first]!=0&&b[i]!=a[i-first]) first+=kmp[i-1-first];
if (b[i]!=a[i-first]) first=-1;
}
}
}
fprintf(g,"%d\n",l);
for(i=1;i<=l;i++) fprintf(g,"%d ",val[i]);
return 0;
}