Pagini recente » Cod sursa (job #2894904) | Cod sursa (job #920666) | Cod sursa (job #2514203) | Cod sursa (job #1309148) | Cod sursa (job #169594)
Cod sursa(job #169594)
#include <fstream.h>
#include <string.h>
#define NM 20000001
char N[NM],M[NM],sol[NM];
int pi[NM];
int main()
{
int k,n,i,m,q,nr=1;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.get(M+1,100);
f.get();
f.get(N+1,100);
n = strlen(N+1);
k = 0;
pi[1] = 0;
for (i = 2; i <= n; i++)
{
while (k>0 && N[k+1]!=N[i])
k=pi[k];
if (N[k+1]==N[i])
k++;
pi[i]=k;
}
m = strlen(M+1); n = strlen(N+1);
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) sol[nr++]=i-n+1;
}
g<<nr-1<<"\n";
for (i=1;i<nr;i++) g<<sol[i]<<" ";
return 0;
}