Pagini recente » Cod sursa (job #873177) | Cod sursa (job #876977) | Cod sursa (job #139682) | Cod sursa (job #2886150) | Cod sursa (job #902109)
Cod sursa(job #902109)
#include<fstream>
#include<cstring>
#define NMAX 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[NMAX],b[NMAX];
int p[NMAX],poz[1005],k,n,m,i,q;
void common(char x[],char y[])
{
while(q && x[q+1]!=y[i])
q=p[q];
if(x[q+1]==y[i])
q++;
}
void prefix()
{
for(i=2,q=0;i<=m;i++)
{
common(a,a);
p[i]=q;
}
}
void kmp()
{
for(i=1,q=0;i<=n;i++)
{
common(a,b);
if(q==m)
{
q=p[m];
k++;
if(k<=1000)
poz[k]=i-m;
}
}
}
void afisare()
{
int i;
g<<k<<'\n';
if(k>1000)
k=1000;
for(i=1;i<=k;i++)
g<<poz[i]<<' ';
g<<'\n';
g.close();
}
void citire()
{
a[0]=b[0]=' ';
f>>(a+1)>>(b+1);
m=strlen(a)-1;
n=strlen(b)-1;
f.close();
}
int main()
{
citire();
prefix();
kmp();
afisare();
return 0;
}