Cod sursa(job #856428)

Utilizator tibi9876Marin Tiberiu tibi9876 Data 16 ianuarie 2013 15:02:31
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<fstream>
#include<string>
using namespace std;

string a,b;
int i,j,n,m,k,c[2000005],v[1005];

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)
		{
			if (k<1000)
				v[++k]=i-j;
			else k++;
		}
	}
	g << k << "\n";
	for (i=1;i<=min(k,1000);i++)
		g << v[i] << ' ';
	return 0;
}