Cod sursa(job #2041993)

Utilizator ilucianIlea Lucian ilucian Data 17 octombrie 2017 22:26:32
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
#include <fstream>
#include <string.h>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
char P[2000002],T[2000002],S[4000004];
int Z[4000004];
int n,m,ck,beta;
int L,R,ind1,ind2;
int rez;
int main()
{
    fi>>P;
    fi>>T;
    n=strlen(P);
    strcpy(S,"*");
    strcat(S,P);
    strcat(S,"$");
    strcat(S,T);
    m=strlen(S+1);
    Z[1]=0;
    L=1;
    R=1;
    for (int k=2;k<=m;k++)
        if (S[k]!=S[1])
            ;
        else
            if (k>R)
            {
                ind1=1;
                ind2=k;
                while (S[ind1]==S[ind2])
                {
                    ind1++;
                    ind2++;
                }
                Z[k]=ind1-1;
                L=k;
                R=ind2-1;
            }
            else
            {
                ck=k-(L-1);
                beta=R-(k-1);
                if (Z[ck]<beta)
                    Z[k]=Z[ck];
                else
                {
                    Z[k]=beta;
                    ind2=R+1;
                    ind1=1+beta;
                    while (S[ind1]==S[ind2])
                    {
                        Z[k]++;
                        ind1++;
                        ind2++;
                    }
                    if (k+Z[k]-1>R)
                    {
                        L=k;
                        R=k+Z[k]-1;
                    }
                }
        }
    /*
    for (int i=1;i<=m;i++)
        fo<<S[i]<<" ";
    fo<<"\n";
    for (int i=1;i<=m;i++)
        fo<<Z[i]<<" ";
    fo<<"\n";
    */
    for (int i=n+2;i<=m;i++)
        if (Z[i]==n)
            rez++;
    fo<<rez<<"\n";
    int nr=0;
    for (int i=n+2;i<=m;i++)
        if (Z[i]==n)
        {
            fo<<i-n-2<<" ";
            nr++;
            if (nr==1000)
                break;
        }
    fi.close();
    fo.close();
    return 0;
}