Cod sursa(job #864925)

Utilizator drobertDumitru Robert drobert Data 25 ianuarie 2013 21:03:56
Problema Potrivirea sirurilor Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int n,m,i,j,k,p,sol[1001],pi[2000001];
char a[2000001],b[2000001];
int main ()
{
	f.get(a,2000001);
	f.get();
	f.get(b,2000001);
	for (n=0;a[n];n++);
	for (m=0;b[m];m++);
	for (i=2;i<=n;i++)
	{
		while (k>0 && a[k+1]!=a[i])
			k=pi[k];
		if (a[k+1]==a[i])
			k++;
		pi[i]=k;
	}
	for (i=1;i<=m;i++)
	{
		while (k>0 && a[k+1]!=b[i])
			k=pi[k];
		if (a[k+1]==b[i])
			k++;
		if (k==n-1)
		{
			p++;
			sol[p]=i-n+1;
		}
	}
	g<<p<<'\n';
	for (i=1;i<=p;i++)
		g<<sol[i]<<" ";
	
	return 0;
}