Cod sursa(job #611782)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 3 septembrie 2011 12:54:03
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<fstream>
#include<cstring>
using namespace std;
int n,m,Urm[2000005],nrsol,sol[1005];
char T[2000005],P[2000005];

void Citire()
{
	int i;
	ifstream fin("strmatch.in");
	fin>>P;
	fin>>T;
	fin.close();
	n=strlen(T);
	m=strlen(P);
	//indexez sirurile de la 1
	for(i=n;i>0;i--)
		T[i]=T[i-1];
	for(i=m;i>0;i--)
		P[i]=P[i-1];
}

void Urmatorul(char *P)
{
	int k=0,x;
	Urm[1]=0;
	for(x=2;x<=m;x++)
	{
		while(k && P[k+1]!=P[x]) k=Urm[k];
		if(P[k+1]==P[x]) k++;
		Urm[x]=k;
	}
}

void Rezolvare()
{
	int i,x=0;
	Urmatorul(P);
	for(i=1;i<=n;i++)
	{
		while(x && P[x+1]!=T[i]) x=Urm[x];
		if(P[x+1]==T[i]) x++; //s-au potrivit
		if(x==m) //am gasit intreg pattern-ul
		{
			nrsol++;
			if(nrsol<=1000)
				sol[nrsol]=i-m;
			x=Urm[x];
		}
	}
}

void Afisare()
{
	int i;
	ofstream fout("strmatch.out");
	fout<<nrsol<<"\n";
	for(i=1;i<=nrsol;i++)
		fout<<sol[i]<<' ';
	fout<<"\n";
	fout.close();
}

int main()
{
	Citire();
	Rezolvare();
	Afisare();
	return 0;
}