Cod sursa(job #856406)

Utilizator tibi9876Marin Tiberiu tibi9876 Data 16 ianuarie 2013 14:30:44
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.52 kb
#include<fstream>
using namespace std;

char a[1000],b[1000];
int i,j,n,m,c[1000];

int main()
{
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	f >> n >> m;
	for (i=1;i<=n;i++)
		f >> a[i];
	for (i=1;i<=m;i++)
		f >> b[i];
	for (i=2;i<=m;i++)
	{
		j=c[i-1];
		while ((b[i]!=b[j+1]) && (j>0))
			j=c[j];
		if (b[i]==b[j+1])
			c[i]=j+1;			
	}
	for (i=1;i<=n;i++)
	{
		while ((a[i]!=b[j+1]) && (j>0))
			j=c[j];
		if (a[i]==b[j+1])
			j++;
		if (j==m)
			g << i-j+1 << ' ';
	}
	return 0;
}