Cod sursa(job #728768)

Utilizator vld7Campeanu Vlad vld7 Data 28 martie 2012 22:43:06
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <cstring>
#include <iostream>
using namespace std;

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

int n, m, urm[2000001], SOL[2000001], NrSol;
char T[2000001];	// textul
char P[2000001];	// pattern

void functie_prefix()
{
	int k=0, i;
	urm[1]=0;
	for(i=2; i<=m; i++)
	{
		while(k>0 && P[k+1]!=P[i])
			k=urm[k];
		if(P[i]==P[k+1])
			k++;
		urm[i]=k;
	}
}

int main()
{
	int i, k;
	f.getline(P, 2000001);		f.getline(T, 2000001);
	n=strlen(T);		// lungimea textului
	m=strlen(P);		// lungimea patternului
	
	for(i=n;i>=1;i--)
		T[i]=T[i-1];
	for(i=m;i>=1;i--)
		P[i]=P[i-1];
	
	functie_prefix();		// construiesc functia prefix
	
	k=0;
	for(i=1;i<=n;i++)
	{
		while(k>0 && T[i]!=P[k+1])
			k=urm[k];
		if(T[i]==P[k+1])		// am gasit inca un caracter corect
			k++;
		if(k==m)		// am gasit solutie
		{
			SOL[++NrSol]=i-k;
			k=urm[k];
		}
	}
	
	g<<NrSol<<'\n';
	for(i=1;i<=NrSol;i++)
		g<<SOL[i]<<" ";
	g<<'\n';
	
	f.close();
	g.close();
	
	return 0;
}