Cod sursa(job #864166)

Utilizator drobertDumitru Robert drobert Data 24 ianuarie 2013 18:31:29
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.54 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m,k,p,v,sol[1002],pi[2000002],i;
char a[2000002],b[2000002];
int main ()
{
	f.get(a,2000002);
	f.get();
	f.get(b,2000002);
	for (n=0;a[n];n++);
	for (m=0;b[m];m++);
	for (i=2;i<=m;i++)
	{
		while (k>0 && a[k+1]!=b[i])
			k=pi[k];
		if (a[k+1]==b[i])
			k++;
		pi[i]=k;
		if (k>=n-1)
		{
			p++;
			sol[p]=i-n+1;
			if (p>1000)
				break;
		}
	}
	g<<p<<'\n';
	for (i=1;i<=p;i++)
		g<<sol[i]<<" ";
}