Pagini recente » Cod sursa (job #1385906) | Cod sursa (job #2415984) | Cod sursa (job #1625476) | Cod sursa (job #2363619) | Cod sursa (job #1394856)
#include<fstream>
#include<cstring>
using namespace std;
char x[2000005],y[2000005];
int pi[2000005],s[2000005];
void prefix();
void kmp();
int lx,ly,sol[1005],u,R;
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
in>>(x+1);
in>>(y+1);
lx=strlen(x+1);
ly=strlen(y+1);
if(lx>ly) {out<<"0\n"; return 0;}
prefix();
kmp();
int i;
for(i=1;i<=ly;++i)
{
if(s[i]==lx)
{
++R;
if(u<1000) sol[++u]=i-lx;
}
}
out<<R<<'\n';
for(i=1;i<=u;++i) out<<sol[i]<<' ';
out<<'\n';
}
void kmp()
{
int k=0,i;
if(x[1]==y[1]) s[1]=1,k=1;
for(i=2;i<=ly;++i)
{
while(x[k+1]!=y[i] && k>0)
{
k=pi[k];
}
if(x[k+1]==y[i])
{
k++;
}
s[i]=k;
}
}
void prefix()
{
int k=0,i;
pi[1]=0;
for(i=2;i<=lx;++i)
{
while(x[k+1]!=x[i] && k>0)
{
k=pi[k];
}
if(x[k+1]==x[i])
{
++k;
}
pi[i]=k;
}
}