Cod sursa(job #1631266)

Utilizator andreiudilaUdila Andrei andreiudila Data 5 martie 2016 14:18:19
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <cstring>
#include <fstream>
#include <iostream>



using namespace std;

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

string a,b;
int pi[2000010],sol[1005],n,m,total,i;

void buildprefix()
{
	int i, q = 0;
    pi[0]=-1;

	for (i = 1; i <m; ++i)
	{
	    q=pi[i-1];

		while (q>=0 && a[q] != a[i])
			q = pi[q];

		pi[i] = q+1;
	}
}




int main()
{

    getline(fin, a);
    getline(fin, b);
	m = a.length();
    n = b.length();

	if(m > n)
		{ fout<<"0"; return 0; }


	buildprefix();

	int q = 0;
	for ( i = 0; i<n; ++i)
	{
		while (q>0 && a[q] != b[i])
			q = pi[q-1];

			//if(q<0) q=0;

		if (a[q] == b[i])
			++q;

		if (q == m)
		{
			q = pi[m-1];

            ++total;
			if(total < 1000)
				sol[total] = i-m+1;
		}
	}

	fout<<total<<"\n";
	for(i=1;i<=min(total, 1000); i++)
		fout<<sol[i]<<" ";

    return 0;
}