Pagini recente » Cod sursa (job #2338246) | Cod sursa (job #2038768) | Cod sursa (job #1454224) | Cod sursa (job #2038633) | Cod sursa (job #278499)
Cod sursa(job #278499)
#include<fstream>
#include<string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char n[2000001],m[2000001];
long N,M;
long pi[2000001],x[1005],c;
void pref()
{ long i,k;
k=0;
for(i=2,pi[1]=0;i<=N;i++)
{ while(k>0&&n[k+1]!=n[i])
k=pi[k];
if(n[k+1]==n[i])
k++;
pi[i]=k;
}
}
void kmp()
{ long q,i;
q=0;
pref();
for(i=1;i<=M;i++)
{ while(q>0&&n[q+1]!=m[i])
q=pi[q];
if(n[q+1]==m[i])
q++;
if(q==N)
{ c++;
q=pi[N];
if(c<=1000)
x[c]=i-N;
}
}
}
int main()
{ fin>>n>>m;
long i;
M=strlen(m);
N=strlen(n);
for(i=N;i>=0;i--)
n[i]=n[i-1];
n[0]=' ';
for(i=M;i>=0;i--)
m[i]=m[i-1];
m[0]=' ';
kmp();
fout<<c<<" \n";
if(c>1000) c=1000;
for(i=1;i<=c;i++)
fout<<x[i]<<" ";
fin.close();
fout.close();
return 0;
}