Pagini recente » Cod sursa (job #2447164) | Istoria paginii runda/oji_go_10 | Cod sursa (job #690574) | Cod sursa (job #1684723) | Cod sursa (job #850411)
Cod sursa(job #850411)
#include<fstream>
#include<cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int i,n,m,nr,v[2000009],urm[2000009];
char s1[2000009],s2[2000009];
void prefix(char s1[])
{
int i,k=-1;
urm[0]=-1;
for(i=1;i<n;++i)
{
while(k!=-1&&s1[i]!=s1[k+1])
k=urm[k];
if(s1[i]==s1[k+1])
++k;
urm[i]=k;
}
}
void kmp(char s2[],char s1[])
{
int i,k=-1;
for(i=0;i<m;++i)
{
while(k!=-1&&s2[i]!=s1[k+1])
k=urm[k];
if(s2[i]==s1[k+1])
++k;
if(k==n-1)
++nr,v[nr]=i-n+1,k=urm[k];
}
}
int main()
{
f>>s1>>s2;
n=strlen(s1);
m=strlen(s2);
prefix(s1);
kmp(s2,s1);
g<<nr<<'\n';
nr=min(nr,1000);
for(i=1;i<=nr;++i)
g<<v[i]<<' ';
return 0;
}