Cod sursa(job #856414)

Utilizator tibi9876Marin Tiberiu tibi9876 Data 16 ianuarie 2013 14:51:42
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<fstream>
#include<string>
using namespace std;

string a,b;
int i,j,n,m,k,c[1000],v[1001];

int main()
{
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	getline(f,b);
	getline(f,a);
	m=b.length();
	n=a.length();
	for (i=n;i>=1;i--)
		a[i]=a[i-1];
	for (i=m;i>=1;i--)
		b[i]=b[i-1];
	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)
		{
			v[++k]=i-j;
			if (k==1000)
				break;
		}
	}
	g << k << "\n";
	for (i=1;i<=k;i++)
		g << v[i] << ' ';
	return 0;
}