Pagini recente » Cod sursa (job #1956364) | Cod sursa (job #2622306) | Cod sursa (job #3235865) | Cod sursa (job #338501) | Cod sursa (job #792594)
Cod sursa(job #792594)
#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("kmp.in");
ofstream fout("kmp.out");
int m,n,k,pi[100],q,x,v[1001];
char M[100],N[100];
int main()
{
int i;
fin>>N;fin>>M;
n=strlen(N);
m=strlen(M);
for(i=n;i>=1;--i) N[i]=N[i-1];
for(i=m;i>=1;--i) M[i]=M[i-1];
k=0;
pi[1]=0;
for(i=2;i<=n;++i)
{ //functia prefix
while(k>0 && N[k+1]!=N[i])
k=pi[k];
if(N[k+1]==N[i]) k++;
pi[i]=k;
}
q=0;
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)
{
x++;
if(x<=1000)
v[x]=i-n;
}
}
fout<<x<<"\n";
for(i=1;i<=x;++i)
fout<<v[i]<<" ";
}