Cod sursa(job #1839116)

Utilizator flibiaVisanu Cristian flibia Data 2 ianuarie 2017 14:35:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 2000006;

string s1, s2; int m, n;
int text[NMAX], pi[NMAX], pos[1010], k;

void KMP(){
	pi[1] = 0;
	int i = 0;
	for(int j = 2; j <= m; j++){
		while(i > 0 && s1[i+1] != s1[j])
			i = pi[i];	
		if(s1[i+1] == s1[j]) i++;
		pi[j] = i;
	}
}

int main(){
	in >> s1 >> s2;
	s1 = '|' + s1;
	s2 = '|' + s2;
	m = s1.size()-1;
	n = s2.size()-1;
	KMP();
	int i = 0;
	for(int j = 1; j <= n; j++){
		while(i > 0 && s1[i+1] != s2[j])
			i = pi[i];
		if(s1[i+1] == s2[j]) i++;
		if(i == m){
			//if(k < 1000) pos[++k] = j-m;
			i = pi[i];
			k++;
			if(k <= 1000) pos[k] = j-m;
		}
	}
	out << k << '\n';
	for(int j = 1; j <= min(1000, k); j++) out << pos[j] << ' ';
	return 0;
}