Pagini recente » Profil Andrei_Cotor | Stalpisori | Rating Stancioiu Silviu (Silviu408) | Cod sursa (job #2004678) | Cod sursa (job #2480856)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000001],b[2000001];
int ap[2000001],n,m,cont,sirsol[2000001];
void citire()
{
f.get(a+1,2000001);
f.get();
f.get(b+1,2000001);
//a[0]='*';
//b[0]='*';
}
void gensufx()
{
int k=0;
for(int i=2;i<=n;i++)
{
while(k!=0&&a[i]!=a[k+1])
k=ap[k];
if(a[i]==a[k+1])
k++;
ap[i]=k;
}
}
void KMP()
{
int k=0;
for(int i=1;i<=m;i++)
{
while(k>0&&b[i]!=a[k+1])
k=ap[k];
if(b[i]==a[k+1])
k++;
if(k==n)
sirsol[++cont]=i-k;
}
}
void afis()
{
g<<cont;
g<<'\n';
for(int i=1;i<=cont;i++)
{
if(i%1000==0)
g<<'\n';
g<<sirsol[i]<<' ';
}
}
int main()
{citire();
n=strlen(a+1);
m=strlen(b+1);
gensufx();
KMP();
//cout<<a<<'\n'<<b;
afis();
return 0;
}