Cod sursa(job #1204326)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 2 iulie 2014 17:23:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include<fstream>
#include<cstring>

using namespace std;

const int NMAX = 2000000+5;

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

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

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

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

    return 0;
}

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

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

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

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

    L=R=0;
    for(i=1; i<N; i++)
        if(i>R)
        {
            L=R=i;
            while(A[R-L]==A[R] && R<N) 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(A[R-L]==A[R] && R<N) R++;
                R--;
                Z[i]=R-L+1;
            }
        }
}

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

    // P[i] = lungimea celui mai lung prefix al lui A care incepe de pe B[i]

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

void print()
{
    int i;

    fout<<nrMatches<<'\n';

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