Cod sursa(job #910701)

Utilizator stef1995mmarcu stefan ovidiu stef1995m Data 10 martie 2013 22:52:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int maxx=2000005;
string a,b;
int z[2*maxx],An,nrcomp,sol[1005];
void read()
{
	getline(f,b);
	a+='#'+b;
	An=b.length();
	getline(f,b);
	a+='#'+b;
}
int main()
{
	read();
	int i,n=a.length(),l=1,r=1,j;
	z[1]=An;
	for(i=2;i<=n;i++)
	{
		if(i>r)
		{
			for(j=1;i+j-1<=n && a[i+j-1]==a[j];j++);
			z[i]=j-1;
			if(j-1)
			{
				l=i;
				r=i+z[i]-1;
			}
		}
		else
			if(z[i-l+1]<r-i+1)
				z[i]=z[i-l+1];
			else
			{
				if(z[i-l+1]>r-i+1)
					z[i]=r-i+1;
				else
				{
					for(++r,j=z[i-l+1]+1;r<=n && a[r]==a[j];r++,j++);
					r--; j--;
					z[i]=j;
					l=i;
				}
			}
		if(z[i]==An)
		{
			nrcomp++;
			if(nrcomp<=1000)
				sol[nrcomp]=i-An-2;
		}
	}
	g<<nrcomp<<"\n";
	for(i=1;i<=min(1000,nrcomp);i++)
		g<<sol[i]<<" ";
	g<<"\n";
	return 0;
}