Cod sursa(job #1168578)

Utilizator dimitriepirghiePirghie Dimitrie dimitriepirghie Data 9 aprilie 2014 00:19:05
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<fstream>
#include<string>
#include<algorithm>
using namespace std;
string A, B;
int esec[2000001], i, k, sol[1005], nrSol=0;
void makeprefix()
{
	esec[0] = -1; 
	for (i = 1; i < A.size(); i++)
	{
		k = i - 1;
		while (k > 0 && A[esec[k] + 1] != A[i])
			k = esec[k];
		esec[i] = esec[k] + 1;
	}
}
int main()
{
	ifstream fin("strmatch.in");
	ofstream fout("strmatch.out");
	getline(fin, A);
	getline(fin, B);
	A = ' ' + A;
	makeprefix();
	k = 0;
	for (i = 1; i < B.length(); i++)
	{
		while (k>0 && (A[k+1] != B[i]))
			k = esec[k];
		if (B[i] == A[k + 1])
			k++;
		if (k == A.length() - 1)
		{
			nrSol++;
			if (nrSol <= 1000)
				sol[nrSol] = i - (A.length() - 1);
			k = esec[k];
		}
	}
	fout<<nrSol << "\n";
	for (i = 1; i <= min(nrSol, 1000); i++)
		fout << sol[i] << " ";

}