Cod sursa(job #978242)

Utilizator petrutsxMihaela Petruta Gaman petrutsx Data 28 iulie 2013 14:19:10
Problema Potrivirea sirurilor Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<fstream>
#include<iostream>
#include<string>
#define NMAX 2000001
using namespace std;

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

int sol[NMAX];
int pi[NMAX];
string A, B;
int dim = 0;

void read(){
	f>>A;
	f>>B;
}

void KMP_prefix(string A){
	int k = 0, N, i;
	N = A.size();
	pi[k] = 0;
	for(i = 1; i < N; i++){
		while(k > 0 && A[k] != A[i])
			k = pi[k];
		if(A[k] == A[i])
			k++;
		pi[i] = k;
	}
}

void KMP_match(string A, string B){
	int t = 0, N = A.size(), M = B.size();
	int i = 0;

	while(i < M){
		while(t > 0 && A[t] != B[i])
			t = pi[i];
		if(A[t] == B[i])
			t++;
		if(t == N){
			sol[dim] = i - N + 1;
			dim++;
			i = i - N + 2;
		}
		else
			i++;
	}
}

void print(){
	int i;
	g<<dim<<"\n";
	for(i = 0; i < dim; i++)
		g<<sol[i]<<" ";
}

int main(){
	read();

	KMP_prefix(A);
	KMP_match(A, B);

	print();

	return 0;
}