Cod sursa(job #1196664)

Utilizator MarianMMorosac George Marian MarianM Data 8 iunie 2014 17:35:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <vector>
#include <string>
using namespace std;

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

#define DMAX 2000001

string P, T;
vector<int> S;
int Prefix[DMAX];

int main(){
	int i, j, M, N, lg, s; char x;

	fin >> P; fin.get(x); fin >> T;
	P = ' ' + P; T = ' ' + T;

	M = P.size();
	for (Prefix[1] = 0, j = 0, i = 2; i < M; i++){
		while (P[j + 1] != P[i] && j)	j = Prefix[j];
		if (P[j + 1] == P[i])			j++;
		Prefix[i] = j;
	}

	N = T.size(); M--;
	for (j = 0, s = 1; s < N; s++){
		while (P[j + 1] != T[s] && j)	j = Prefix[j];
		if (P[j + 1] == T[s])			j++;

		if (j == M)	S.push_back(s), j = Prefix[j];
	}

	lg = S.size();
	fout << lg << '\n';
	for (i = 0; i < lg; i++)	fout << S[i] - M << ' ';

	return 0;
}