Cod sursa(job #169658)

Utilizator g3ppyStoian Vlad g3ppy Data 1 aprilie 2008 20:43:36
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream.h>
#include <string.h>
#define NM 2000002
char N[NM],M[NM];
int pi[NM];

int main()

{
int k,n,i,m,q,nr=1,x;

ifstream f("strmatch.in");
ofstream g("str2.out");

f.get(N+1,NM);
f.get();
f.get(M+1,NM);

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)
       {
       g<<i-n<<" ";
       nr++;
       }

    }
f.close();
g.close();
ifstream f2("str2.out");
ofstream g2("strmatch.out");


g2<<nr-1<<"\n";
for (i=1;i<nr;i++)
    {
    f2>>x;
    g2<<x<<" ";
    }
f2.close();
g2.close();

return 0;
}