Cod sursa(job #1812105)

Utilizator radu.leonardoThe Doctor radu.leonardo Data 21 noiembrie 2016 20:43:54
Problema Potrivirea sirurilor Scor 28
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
///Z-Algorithm
///radu.leonardo
#include<iostream>
#include<fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string pattern,text,concat;
int Z[4000000],sol[100000],nr=0,n,m;

void compute_Z()
{	n=concat.length();
	int L=-1,R=-1, k;
	for (int i=1;i<n;++i)
	{
		if (i>R)
		{	L=R=i;
			while(R<n&&concat[R-L]==concat[R])R++;
			Z[i]=R-L;R--;
        }
		else
		{	k=i-L;
			if (Z[k]<R-i+1)	Z[i]=Z[k];
			else
			{	L=i;
				while(R<n&&concat[R-L]==concat[R])R++;
				Z[i]=R-L;R--;
			}
		}
	}
}

int main()
{	f>>pattern>>text;
    m=pattern.length();
    concat=pattern+text;
    compute_Z();
    for (int i = 0; i < n; ++i)	if (Z[i] == m)	sol[++nr]=i - m;
	g<<nr<<'\n';
	for(int i=1;i<=nr;i++) g<<sol[i]<<' ';
}