Cod sursa(job #631573)

Utilizator sunt_emoSunt emo sunt_emo Data 8 noiembrie 2011 18:41:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 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,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;
	k=2;
	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;
}