Cod sursa(job #1216264)

Utilizator andreas.chelsauAndreas Chelsau andreas.chelsau Data 3 august 2014 23:38:41
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
using namespace std;
typedef unsigned int uint;

int fail[2000000 + 5],n,m;
char p[2000000 + 10],w[2000000 + 10];
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++;
			}
		}
	}
}

void kmp(){
	vector<int> fin;
	uint i = 0,j = 0,c = 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){			
			c++;
			if(c < 1000)
				fin.push_back(i - j);
			i = i - j + 1;
			j = 0;
		}
		
	}
	printf("%d\n",c);
	for(i = 0; i < fin.size(); i++)
		printf("%d ", fin[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;
}