Cod sursa(job #573540)

Utilizator bacilaBacila Emilian bacila Data 6 aprilie 2011 12:53:36
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include <iostream>
#include <fstream>
using namespace std;
char s[2000010],ss[2000010];
int pi[2000010],rez[1005],n,i,q,m;
int main ()
{ifstream f("strmatch.in");
f.getline(s,2000010);
f.getline(ss,2000010);
m=strlen(s);
for(i=1;s[i];i++)
{while(q&&s[q]!=s[i])
q=pi[q];
if(s[q]==s[i])
q++;
pi[i]=q;
}
q=0;
for(i=1;ss[i];i++)
{while(q&&s[q]!=ss[i])
q=pi[q];
if(s[q]==ss[i])
q++;
if(q==m)
{q=pi[m-1];
n++;
if(n<=1000)
rez[n]=i-m;}
}
ofstream g("strmatch.out");
g<<n<<'\n';
if(n>1000)
n=1000;
for(i=1;i<=n;i++)
g<<rez[i]+1<<" ";
 f.close(); g.close();
return 0;
}