Cod sursa(job #830554)

Utilizator Theorytheo .c Theory Data 7 decembrie 2012 01:28:36
Problema Potrivirea sirurilor Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<fstream>
#include<string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[2000007];
char h[2000006];
int H[2000005];
int ret[1008];
int nr,M;
void read(){
	fin >> h + 1;
	M=strlen(h + 1);
	fin >> s + 1;
}

void solve(){
	int k = 0 ;
	H[1] = 0;
	for(int i = 2; h[i]; i++){
			
			while(k > 0 && 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; s[i]; i++){
		if(q > 0&& s[i] != h[q + 1])
			q = H[q];
		if(s[i] == h[q + 1])
			q++;
		
		if(q == M ){
			if(nr <1000)
			ret[++nr] = i - q ;
			q = H[M];
		}
			
	}
	fout << nr <<'\n'; 
	for(int i = 1; i <=min(1000, nr); i++)
		fout<< ret[i] <<" ";
	
	fin.close();
	return 0;
}