Cod sursa(job #428320)

Utilizator loginLogin Iustin Anca login Data 29 martie 2010 10:00:32
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
# include <fstream>
# include <algorithm>
# include <iostream>
# include <cstring>
# define DIM 2000002
# define NMAX 2000
using namespace std;
char a[DIM], b[DIM];
int n, m, N, urm[DIM], p[DIM];

void read ()
{
	ifstream fin ("strmatch.in");
	fin.getline(a, DIM);
	fin.getline(b, DIM);
	m=strlen(a);
	n=strlen(b);
}

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

void potrivire ()
{
	int x=-1;
	for (int i=0;i<n;++i)
	{
		while (x>0 && a[x+1]!=b[i])x=urm[x];
		if (a[x+1]==b[i])++x;
		if (x==m-1)
		{
			p[++N]=i-m+1;
			x=urm[x];
		}
	}
}

void afisare ()
{
	ofstream fout ("strmatch.out");
	fout<<N<<endl;
	int M;
	sort(p+1, p+N+1);
	M=N;
	if (N>1000)
		M=1000;
	for (int i=1;i<=M;i++)
		fout<<p[i]<<" ";
}

int main ()
{
	read ();
	urmatorul();
	potrivire ();
	afisare();
	return 0;
}