Cod sursa(job #1184632)

Utilizator stef93Stefan Gilca stef93 Data 13 mai 2014 18:03:35
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <iostream>
#include <cstring>

using namespace std;

char deCautat[2000003], sir[2000003];
int gasit[1003] , urm[2000003];
int nrGasite , lenCaut , lenSir;

void creareUrm()
{
	int k = 0, i;
	urm[1] = 0;

	for (i = 2; i <= lenCaut; i++)
	{
		while (k > 0 && deCautat[k + 1] != deCautat[i])
		{
			k = urm[k];
		}

		if (deCautat[k + 1] == deCautat[i])
		{
			k++;
		}

		urm[i] = k;
	}
}

int main()
{
	ifstream in("strmatch.in");
	ofstream out("strmatch.out");

	deCautat[0] = 'q';
	deCautat[1] = 'q';
	sir[0] = 'q';
	sir[1] = 'z';
	in >> (deCautat + 1);
	in >> (sir + 1);
	lenSir = strlen(sir) - 1;
	lenCaut = strlen(deCautat) - 1;
	creareUrm();
	int k = 0, i;

	for (i = 1; i <= lenSir; i++)
	{
		while (k > 0 && deCautat[k + 1] != sir[i])
		{
			k = urm[k];
		}

		if (deCautat[k + 1] == sir[i])
		{
			k++;
		}

		if (k == lenCaut)
		{
			nrGasite++;
			if (nrGasite > 10000)
			{
				nrGasite--;
				break;
			}
			else
			{
				gasit[nrGasite - 1] = i - k;
			}
			k = urm[k];
		}
	}

	out << nrGasite << '\n';

	for (i = 0; i < nrGasite; i++)
	{
		out << gasit[i] << ' ';
	}

	in.close();
	out.close();
	return 0;
}