Pagini recente » Cod sursa (job #1320993) | Cod sursa (job #1672480) | Cod sursa (job #1560251) | Cod sursa (job #47080) | Cod sursa (job #1804895)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int urm[2000001],m,n,v[2000001],l;
char t[2000001],p[2000001];
void prefix()
{
int q,k;
k=0;
urm[1]=0;
for(q=2; q<=m; q++)
{
while(k>0 && p[k]!=p[q-1])k=urm[k];
if(p[k]==p[q-1])k++;
urm[q]=k;
}
/* for(q=1;q<=m;q++)
cout<<urm[q]<<" ";cout<<endl;*/
}
void kmp()
{
int q,nr=0,k=0;
for(q=0; q<n; q++)
{
while(k>0 && p[k]!=t[q])
k=urm[k];
if(p[k]==t[q])k++;
if(k==m)
{
v[++nr]=q-m+1;
}
}
g<<nr<<'\n';
for(int i=1;i<=nr && i<=1000;i++)
g<<v[i]<<" ";
}
int main()
{
f.getline(p,2000001);
f.getline(t,2000001);
n=strlen(t);
m=strlen(p);
prefix();
kmp();
return 0;
}