Cod sursa(job #1812132)

Utilizator radu.leonardoThe Doctor radu.leonardo Data 21 noiembrie 2016 20:57:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 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[1000],nr=0;

void compute_Z()
{   int n=concat.length();
    int L=0,R=0, 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;
    concat = pattern + "$" + text;
    compute_Z();
    int l = concat.length();
    for (int i = 0; i < l; ++i)  if (Z[i] == pattern.length())   sol[++nr]=i - pattern.length() -1;
    g<<nr<<'\n';
    for(int i=1;i<=min(nr,1000);i++) g<<sol[i]<<' ';
}