Cod sursa(job #1077986)

Utilizator sorin2kSorin Nutu sorin2k Data 11 ianuarie 2014 21:28:47
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include<fstream>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char text[2000001], pattern[2000001];
int pi[2000001], text_len, pat_len, i, nr;
queue<int> que;

void compute_prefix_function() {
	int k, q;
	k = 0;
	pi[1] = 0;
	for(q = 2; q < pat_len; q++) {
		while(k > 0 && pattern[k+1] != pattern[q]) {
			k = pi[k];
		}
		if(pattern[k+1] == pattern[q]) {
			k++;
		}
		pi[q] = k;
	}
}

void kmp() {
	int k, i;
	k = 0;
	for(i = 1; i < text_len; i++) {
		while(k > 0 && pattern[k+1] != text[i]) {
			k = pi[k];
		}
		if(pattern[k+1] == text[i]) {
			k++;
		}
		if(k == pat_len-1) { // am pus -1 pentru ca pat_len include si primul caracter
			nr++;
			if(nr < 1000) que.push(i-pat_len+1);
			k = pi[k];
		}
	}
}

int main() {
	pattern[0] = text[0] = '-';
	fin >> (pattern+1) >> (text+1);
 	text_len = strlen(text);
	pat_len = strlen(pattern);
	compute_prefix_function();
	kmp();
	fout << nr << '\n';
	while(!que.empty()) {
		fout << que.front() << " ";
		que.pop();
	}
	return 0;
}