Cod sursa(job #910697)

Utilizator stef1995mmarcu stefan ovidiu stef1995m Data 10 martie 2013 22:44:50
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
const int maxx=2000005;
string a,b;
int z[2*maxx],An,nrcomp;
vector <int> sol;
void read()
{
	getline(std::cin,b);
	a+='#'+b;
	An=b.length();
	getline(std::cin,b);
	a+='#'+b;
}
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	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.push_back(i-2-An);
		}
	}
	printf("%d\n",nrcomp);
	for(i=0;i<sol.size();i++)
		printf("%d ",sol[i]);
	printf("\n");
	return 0;
}