Cod sursa(job #830546)

Utilizator Theorytheo .c Theory Data 7 decembrie 2012 01:17:20
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<fstream>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[200007];
char h[200006];
int H[200005];
int ret[200007];
int nr;
void read(){
	fin >> h + 1;
	fin >> s + 1;
}

void solve(){
	int k = 0 ;
	H[1] = 0;
	for(int i = 2; i <=strlen(h + 1); i++){
			
			while(k && h[i] != h[k + 1])
				k = h[k];
		if(h[k + 1] == h[i])
			k++;
		H[i] = k;
	}
}
int main(){
	read();
	solve();
	int q = 0; 
	for(int i = 1; i <= strlen(s + 1); i++){
		if(q && s[i] != h[q + 1])
			q = H[q];
		if(s[i] == h[q + 1])
			q++;
		
		if(q == strlen(h + 1) )
			ret[++nr] = i - q ;
			
	}
	fout << nr <<'\n'; 
	for(int i = 1; i <= nr; i++)
		fout<< ret[i] <<" ";
	
	fin.close();
	return 0;
}