Cod sursa(job #1812127)

Utilizator radu.leonardoThe Doctor radu.leonardo Data 21 noiembrie 2016 20:55:08
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 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[20000000],sol[100000],nr=0,n,m;

void compute_Z() {
    n=concat.length();
    int L=-1,R=-1;

    for(int i=1;i<n;i++)
    {
        if(i>R)
        {  if(concat[0]==concat[i])
           {L=i;
            R=i-1;
            for(int j = 0, k = i; k < n && concat[j] == concat[k]; j++, k++) Z[i] ++,R ++;
           }
           else Z[i] = 0;

        }
        else
        {int before = i - L;
            if(Z[before] < R - i + 1)  Z[i]=Z[before];
            else {Z[i]=R-i+1;
                  L = i;
                  for(int before = Z[i]; R + 1 <n && concat[R + 1] == concat[before]; before++, R++)    Z[i] ++;
                 }
        }
    }
}

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