Cod sursa(job #964914)

Utilizator sorin2kSorin Nutu sorin2k Data 22 iunie 2013 18:46:51
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<fstream>
#include<iostream>
#include<cstring>

using namespace std;

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

char a[2000001], b[2000001];
int n, m, i, pi[2000001], 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 = 0; 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 >> a;
	n = strlen(a);
	fin >> b;
	m = strlen(b);
	calcul_functie_prefix();
	kmp();
	fout << r << endl;
	if(r > 1000)
		r = 1000;
	for(i = 0; i < r; i++)
		fout << raspuns[i] << " ";
	return 0;
}