Cod sursa(job #694195)

Utilizator bacilaBacila Emilian bacila Data 27 februarie 2012 19:13:19
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream>
using namespace std;
char a[2000005],b[2000005];
int v[2000005],rez[1005],n,i,q,sol;
int main ()
{ifstream f("strmatch.in");
 ofstream g("strmatch.out");
 f.getline(a+1,2000003);
 f.getline(b,2000003);
 n=strlen(a+1);
 
 for(i=2;a[i];i++)
 {q=v[i-1];
 while(q&&a[q+1]!=a[i])
 q=v[q];
 if(a[q+1]==a[i])
 v[i]=q+1;
 else
 v[i]=q;
 }
 for(i=0;b[i];i++)
 
 if(b[i]==a[q+1])
 {q++;
 if(q==n)
 {sol++;
 if(sol<=1000)
 rez[sol]=i-n+1;
 q=v[n];
 }
}
 else
 q=v[q];
 g<<sol<<'\n';
 if(sol>1000)
 sol=1000;
 for(i=1;i<=sol;i++)
 g<<rez[i]<<" ";
 f.close(); g.close();
return 0;
}