Cod sursa(job #1631289)

Utilizator andreiudilaUdila Andrei andreiudila Data 5 martie 2016 14:31:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 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;
    pi[1]=0;

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

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

		pi[i] = q+1;
	}
}

int main()
{

    getline(fin, a);
    getline(fin, b);

	m = a.length();
    n = b.length();

    a=' '+a;
    b=' '+b;

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


	buildprefix();

	int q = 0;

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

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

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

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

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

    return 0;
}