Cod sursa(job #2041573)

Utilizator FredyLup Lucia Fredy Data 17 octombrie 2017 17:01:59
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 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]=n;
    l=1;
    r=1;
    for (int k=2;k<=m;k++)
        if (k>r)
        {
            ind1=1;
            ind2=k;
            while (S[ind1]==S[ind2])
            {
                ind1++;
                ind2++;
            }
            Z[k]=ind1-1;
            if (Z[k]!=0)
            {
                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=ind2-(k-1);
                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";
    for (int i=n+2;i<=m;i++)
        if (Z[i]==n)
            fo<<i-n-2<<" ";
    fi.close();
    fo.close();
    return 0;
}