Pagini recente » Cod sursa (job #25978) | Cod sursa (job #3294463) | Cod sursa (job #3277917) | Cod sursa (job #2585510) | Cod sursa (job #2469365)
#include <fstream>
#include <iostream>
#define NMAX 2000001
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[NMAX],b[NMAX];
int lp[NMAX]={0};
void make_prefix(char *v,int *lps)
{
int len=0,i=1;
lps[0]=0;
while(v[i]!='\00')
{
if(v[i]==v[len])
{
++len;
lps[i]=len;
++i;
}
else
{
if(len)
len=lps[len-1];
else
{
lps[i]=0;
++i;
}
}
}
}
int main()
{
f.getline(a,NMAX,'\n');
f.getline(b,NMAX,'\n');
make_prefix(a,lp);
int i=0,j=0,nr=0,v[1000];
while(b[j]!='\00')
{
if(a[i]==b[j])
{
++i;
++j;
}
if(a[i]=='\00')
{
v[nr++]=j-i;
if(nr==1000)
break;
i=lp[i-1];
}
else if(b[j]!='\00' && a[i]!=b[j])
{
if(i)
i=lp[i-1];
else
++j;
}
}
g<<nr<<'\n';
for(i=0;i<nr;++i)
g<<v[i]<<' ';
return 0;
}