Pagini recente » Cod sursa (job #1032137) | Cod sursa (job #2624047) | Cod sursa (job #526596) | Cod sursa (job #966391) | Cod sursa (job #2364725)
#include <cstdio>
#define N 2000004
#include <cstring>
#include <iostream>
using namespace std;
FILE *f,*g;
char c1[N],c2[N];
int lg1,lg2,pi[N],sol,v[1002];
void kmp()
{
int k=0;
for(int i=1;i<=lg2;++i)
{
while(k && c1[k+1]!=c2[i])
k=pi[k];
if(c1[k+1]==c2[i])
++k;
if(k==lg1)
{
if(sol<1000)
v[++sol]=i;
else
++sol;
}
}
}
void kmp1()
{
int k=0;
for(int i=2;i<=lg1;++i)
{
while(k && c1[k+1]!=c1[i])
k=pi[k];
if(c1[k+1]==c1[i])
++k;
pi[i]=k;
}
}
int main()
{
f=fopen("strmatch.in","r");
g=fopen("strmatch.out","w");
fgets(c1+1,N,f);
fgets(c2+1,N,f);
lg1=strlen(c1+1);
c1[lg1]=NULL;
--lg1;
lg2=strlen(c2+1);
c2[lg2]=NULL;
--lg2;
kmp1();
kmp();
fprintf(g,"%d\n",sol);
sol=min(sol,1000);
for(int i=1;i<=sol;++i)
fprintf(g,"%d ",v[i]-lg1);
fclose(f);
fclose(g);
return 0;
}