Cod sursa(job #1216331)

Utilizator andreas.chelsauAndreas Chelsau andreas.chelsau Data 4 august 2014 10:35:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;
typedef unsigned int uint;

uint fail[2000000 + 5],n,m,poz[1001];
char p[2000000 + 10],w[2000000 + 10];
inline void failure(){
	uint i = 1,j = 0;
	while(i < m){
		if(p[i] == p[j]){
			fail[i] = ++j;
			i++;
		}
		else{
			if(j != 0)
				j = fail[j - 1];
			else{
				fail[i] = 0;
				j = 0;
				i++;
			}
		}
	}
}

inline void kmp(){
	uint i = 0,j = 0,c = 0,k = 0;
	for(i = 0; i < n; ){
		if(w[i] == p[j]){
			j++;
			i++;
		}
		else{
			if(j != 0)
				j = fail[j - 1];
			else{
				j = 0;
				i++;
			}
		}
		if(j == m){	
			if(c < 1000)
				poz[c] = i - j;
			c++;	
		}
		
	}
	printf("%d\n",c);
	uint max = c >= 1000 ? 1000 : c;
	for(i = 0; i < max; i++)
		printf("%d ", poz[i]);

}

int main(){
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);

	fgets(p,sizeof(p),stdin);
	fgets(w,sizeof(w),stdin);
	for(; p[m] > 0; m++);
	m--;
	for(; w[n] > 0; n++);
	failure();
	kmp();
	return 0;
}