Cod sursa(job #671076)

Utilizator federerUAIC-Padurariu-Cristian federer Data 30 ianuarie 2012 17:39:15
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<fstream>
#include<string>
using namespace std;

char T[2000001], P[2000001];
long p, t, k, L[200000], D[2000001], m, n, i;

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

int main()
{
	fin.getline(P, 2000001);
	fin.getline(T, 2000001);
	m=strlen(P);
	n=strlen(T);
	L[0]=0;
	k=-1;
	for(p=1;p<m;p++)
	{
		while(P[k+1]!=P[p] && k>0)
			k=L[k];
		if(P[k+1]==P[p])
			k++;
		L[p]=k;
	}
	k=-1;
	for(t=0;t<n;t++)
	{
		while(k>0 && T[t]!=P[k+1])
			k=L[k];
		if(T[t]==P[k+1])
			k++;
		if(k==m-1)
		{
			D[++i]=t-m;
			k=L[k];
		}
	}
	fout<<i<<'\n';
	for(p=1;p<=i;p++)
		fout<<D[p]+1<<' ';
	fout<<'\n';
	fin.close();
	fout.close();
	return 0;
}