Cod sursa(job #694260)

Utilizator bacilaBacila Emilian bacila Data 27 februarie 2012 19:33:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <fstream>
#include <cstring>
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,2000003);
 f.getline(b,2000003);
 n=strlen(a);
 
 for(i=1;a[i];i++)
 {
 while(q&&a[q]!=a[i])
 q=v[q];
 if(a[q]==a[i])
 q++;
 
 v[i]=q;
 }
 
 
 q=0;
 for(i=0;b[i];i++)
 {while(b[i]!=a[q]&&q)q=v[q-1];
 if(b[i]==a[q])
 q++;
 if(q==n)
 {sol++;
 if(sol<=1000)
 rez[sol]=i-n+1;
 q=v[n-1];
 }
}

 g<<sol<<'\n';
 if(sol>1000)
 sol=1000;
 for(i=1;i<=sol;i++)
 g<<rez[i]<<" ";
 f.close(); g.close();
return 0;
}