Cod sursa(job #830551)

Utilizator Theorytheo .c Theory Data 7 decembrie 2012 01:21:54
Problema Potrivirea sirurilor Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<fstream>
#include<string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[200007];
char h[200006];
int H[200005];
int ret[1008];
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) ){
			if(nr <1000)
			ret[++nr] = i - q ;
			q = H[q];
		}
			
	}
	fout << nr <<'\n'; 
	for(int i = 1; i <= nr; i++)
		fout<< ret[i] <<" ";
	
	fin.close();
	return 0;
}