Cod sursa(job #704333)

Utilizator ramrumRadu Bozovici ramrum Data 2 martie 2012 17:32:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <cstring>
using namespace std;

#define nmax 2000002
int urm[nmax];
char T[nmax], P[nmax];
int n, m, qq;
bool here[nmax];

void citire()
{
	ifstream in("strmatch.in"); 
	in>>P>>T;
	n = strlen(T); m = strlen(P); 
}


void afisare()
{
	ofstream out("strmatch.out");
	//for(int k=0; k<m; k++)
		//out<<urm[k]<<" ";
	out<<qq<<"\n";
	if(qq > 1000)
		qq = 1000;
	for(int i=0; i<n && qq; i++)
		if(here[i])
		{
			out<<i<<" ";
			qq--;
		}

}

void urmatorul( char p[])
{
	int i, x=-1;
	urm[0] = 0;
	for(i=1; i<m; i++)
	{
		while(x>0 && p[x+1]!=p[i])
			x = urm[x];
		if(p[x+1] == p[i])
			x++;
		urm[i] = x;
	}
}

void kmp()
{
	int i, x=-1;
	for(i=0; i<n; i++)
	{
		while(x>0 && P[x+1]!=T[i])
			x = urm[x];
		if(P[x+1] == T[i])
			x++;
		if(x == m-1)
		{
			here[i-m+1] = true;
			qq++;
			//out<<i-m+1<<"\n";
			x = urm[x];
		}
	}
}
	
int main()
{
	
	citire();
	urmatorul(P);
	kmp();
	afisare();
	return 0;
}