Cod sursa(job #1203867)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 1 iulie 2014 14:29:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include<fstream>
#include<cstring>

using namespace std;

const int NMAX = 2000000+5;

void read();
void z_algorithm();
void print();

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

string A,B,C;
int N,M,P;
int Z[NMAX*2];
int nrMatches;
int matches[1005];

int main()
{
    read();
    z_algorithm();
    print();

    return 0;
}

void read()
{
    fin>>A;
    fin>>B;

    N=A.size();
    M=B.size();
}

void z_algorithm()
{
    int i,k,L,R;

    C=A+' '+B;
    P=N+1+M;

    // Z[i] = lungimea celui mai lung prefix al lui C care incepe de pe C[i]

    L=R=0;
    for(i=1; i<P; i++)
    {
        if(i>R)
        {
            L=R=i;
            while(C[R-L]==C[R] && R<P) R++;
            R--;
            Z[i]=R-L+1;
        }
        else
        {
            k=i-L;
            if(Z[k]<R-i+1) Z[i]=Z[k];
            else
            {
                L=i;
                while(C[R-L]==C[R] && R<P) R++;
                R--;
                Z[i]=R-L+1;
            }
        }
        if(Z[i]==N)
        {
            nrMatches++;
            if(nrMatches<=1000) matches[nrMatches]=i-N-1;
        }
    }
}

void print()
{
    int i;

    fout<<nrMatches<<'\n';

    for(i=1; i<=min(nrMatches,1000); i++)
        fout<<matches[i]<<' ';
}