Cod sursa(job #627186)

Utilizator DuxarFII-Stefan-Negrus Duxar Data 29 octombrie 2011 11:55:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<fstream>
#include<cstring>
using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

char T[2000090],PM[2000090];
int pos[1009],nr,lgT,lgPM,P[2000090];

void P_prefix();
void KMP();

int main()
{
	int a,i;
	f.getline(PM+1,2000090);
	lgPM=strlen(PM+1);
	
	f.getline(T+1,2000090);
	lgT=strlen(T+1);
	
	P_prefix();
	KMP();
	
	g<<nr<<'\n';\
	a=1000;
	if (a>=nr) a=nr;
	for (i=1;i<=a;++i)
		g<<pos[i]<<' ';
	
	f.close();
	g.close();
	return 0;
}

void KMP()
{
	int k,t;
	k=0;
	for (t=1;t<=lgT;++t)
	{
		while (k&&T[t]!=PM[k+1])
			k=P[k];
		if (T[t]==PM[k+1])
			++k;
		if (k==lgPM)
		{
			++nr;
			if (nr<=1000)
				pos[nr]=t-lgPM;
			k=P[k];
		}
	}
}
void P_prefix()
{
	int p,k;
	P[1]=0;
	for (p=2;p<=lgPM;++p)
	{
		k=P[p-1];
		while (PM[k+1]!=PM[p]&&k)
			k=P[k];
		if (PM[k+1]==PM[p])
			++k;
		P[p]=k;
	}
}