Pagini recente » Cod sursa (job #1179877) | Cod sursa (job #174011) | Cod sursa (job #1708862) | Cod sursa (job #1910190) | Cod sursa (job #1801413)
//Potrivire-KMP
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n1,n2,i,k,q,nr,p[20000010],v[20000010],Max;
char sir1[20000010],sir2[20000010];
int main()
{
fin>>sir1;
fin>>sir2;
//fout<<sir1<<"\n"<<sir2;
n1=strlen(sir1);
n2=strlen(sir2);
p[1]=0;
for(i=2;i<=n1;++i)
{
while(k>0 && sir1[k]!=sir1[i-1])
k=p[k];
if(sir1[k]==sir1[i-1])
k++;
p[i]=k;
}
for(i=0;i<n2;++i)
{
while(q>0 && sir1[q]!=sir2[i])
q=p[q];
if(sir1[q]==sir2[i])
q++;
if(q==n1)
{
++nr;
v[nr]=i-n1+1;
}
}
Max=min(nr,1000);
fout<<nr<<"\n";
for(i=1;i<=Max;++i)
{
fout<<v[i]<<" ";
}
return 0;
}