Cod sursa(job #1200091)

Utilizator silidragosSilion Dragos silidragos Data 21 iunie 2014 20:42:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<iostream>
#include<fstream>
#include<string>
#define NMAX 2000005
#define MMAX 2000005
#define minim(a,b) ((a<b)?a:b)

using namespace std;


int N, M,pi[NMAX],pos[1024];
string P, S;

void f_prefix(){
	pi[1] = 0;
	int q = 0;

	for (int i = 2; i < M; ++i){
		while (q && P[q + 1] != P[i]){
			q = pi[q];
		}
		if (P[q + 1] == P[i])
			q++;
		pi[i] = q;

	}

}


int main(){
	ifstream f("strmatch.in", ios::in);//Change the name
	ofstream g("strmatch.out", ios::out);//Change the name
	
	f >> P;
	f >> S;

	P.push_back(' ');
	for (int i = P.size()-1; i; --i)
		P[i] = P[i - 1];
	S.push_back(' ');
	for (int i = S.size() - 1; i; --i)
		S[i] = S[i - 1];

	M = P.size();
	N = S.size();
	f_prefix();

	int q = 0,n = 0;

	for (int i = 1; i < N; ++i){
		
		while (q && P[q + 1] != S[i])
			q = pi[q];
		if (P[q + 1] == S[i])
			q++;
		if (q == M - 1){
			q = pi[M-1];
			++n;
			if (n<=1000)
			pos[n] = i - M +1;
		}
	}

	g << n << '\n';
	for (int i = 1; i <=minim(n,1000); ++i)
		g << pos[i] << ' ';
	g << '\n';




	f.close();
	g.close();
	return 0;
}