Cod sursa(job #964909)

Utilizator sorin2kSorin Nutu sorin2k Data 22 iunie 2013 18:33:03
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<fstream>
#include<iostream>
#include<cstring>

using namespace std;

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

char buff[2000000], *a, *b;
int n, m, i, *pi, raspuns[1000], r;

// functia va calcula un tablou de lungimea strlen(a) (a = sirul de cautat) in care pe pozitia i se va afisa sufixul maxim
// a lui a[i] care e prefix pentru a. (a[i] = sirul format din primele i caractere ale lui a)
void calcul_functie_prefix()
{
	int k = 0;
	for(i = 1; i < n; i++) 
	{
		if(k > 0 && a[i] != a[k])
			k = pi[k]; 
		if(a[i] == a[k])
			k = k + 1;
		pi[i] = k;
	}
}

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

		if(q == n)
		{
			if(r < 1000)
				raspuns[r] = i - q + 1;
			r++;
			q = pi[q - 1];
		}
	}
}

int main()
{
	fin >> buff;
	n = strlen(buff);
	a = new char[n + 1];
	strcpy(a, buff);
	fin >> buff;
	m = strlen(buff);
	b = new char[m + 1];
	strcpy(b, buff);
	pi = new int[n];
	memset(pi, 0, n * sizeof(int));
	calcul_functie_prefix();
	kmp();
	fout << r << endl;
	if(r > 1000)
		r = 1000;
	for(i = 0; i < r; i++)
		fout << raspuns[i] << " ";
	return 0;
}