Cod sursa(job #631580)

Utilizator sunt_emoSunt emo sunt_emo Data 8 noiembrie 2011 19:12:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.48 kb
#include<fstream>
#define N 2000010
std::ifstream in("strmatch.in");std::ofstream out("strmatch.out");char s[N],w[N];int pmt[N],i,k=2,c[N],l,n,m,t;int main(){in.getline(w,N);in.getline(s,N);while(w[++m]);while(s[++n]);pmt[0]=-1;while(k<=m){while(w[k-1]==w[t])pmt[k++]=++t;if(t)t=pmt[t];else pmt[k++]=0;}k=0;while(k+i<n){while(w[i]==s[k+i]&&i<m)i++;if(i==m)c[l++]=k;k+=i-pmt[i];if(pmt[i]>-1) i=pmt[i];else i=0;}out<<l<<"\n";if(l>1000)l=1000;for(i=0;i<l;i++)out<<c[i]<<" ";out<<"\n";return 0;}