Cod sursa(job #1291544)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 12 decembrie 2014 22:05:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <vector>
#include <fstream>
#include <string.h>

using namespace std;

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

const int maxn = 2000005;

char pattern[maxn], text[maxn];
int n, m, pi[maxn];

int main() {
	fin >> pattern + 1 >> text + 1;

	n = strlen(pattern + 1);
	m = strlen(text + 1);
	int k = 0;
	
	for(int i = 2 ; i <= n ; ++ i) {
		while(k > 0 && pattern[i] != pattern[k + 1])
			k = pi[k];
		if(pattern[i] == pattern[k + 1])
			++ k;
		pi[i] = k;
	}
	vector <int> matches;
	k = 0;
	for(int i = 1 ; i <= m ; ++ i) {
		while(k > 0 && text[i] != pattern[k + 1])
			k = pi[k];
		if(text[i] == pattern[k + 1])
			++ k;
		if(k == n)
			matches.push_back(i - k);
	}
	fout << matches.size() << '\n';
	for(int i = 0 ; i < min(1000, int(matches.size())) ; ++ i)
		fout << matches[i] << ' ';
}