Cod sursa(job #478102)

Utilizator zloteanu.adrianzloteanu adrian nichita zloteanu.adrian Data 17 august 2010 13:58:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<fstream>
#include<string.h>
#define NM 2000001
using namespace std;
char t[2000001],p[2000001];
int u[2000001],n,m,s[1001];
void urm()
{int q,k=-1;
u[0]=-1;
for(q=1;q<m;++q)
  {while(k>-1&&p[k+1]!=p[q])
	   k=u[k];
  if(p[k+1]==p[q])
   k++;
  u[q]=k;}}
int main()
{ifstream in("strmatch.in");
ofstream out("strmatch.out");
in>>p>>t;
int i,k=0,q;
m=strlen(p);
n=strlen(t);
urm();
q=-1;
for(i=0;i<n;++i)
  {while(q>-1&&p[q+1]!=t[i])
     q=u[q];
  if(p[q+1]==t[i])
   q++;
  if(q==m-1)
   {k++;
	if(k<=1000)
	s[k]=i-m+1;
   q=u[q];}}
out<<k<<"\n";
for(i=1;i<=k&&i<=1000;++i)
  out<<s[i]<<" ";
return 0;
}