Cod sursa(job #2042983)

Utilizator aturcsaTurcsa Alexandru aturcsa Data 19 octombrie 2017 15:48:48
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <iostream>
#include <string.h>
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char S[40000010],T[2000005];
int n,m,Z[40000010],nrrez;

void calcul(int m, char S[], int Z[])
{
    int L,R,kp,beta;
    Z[1]=0;
    L=1;
    R=1;
    for (int k=2;k<=m;k++)
        if (S[k]!=S[1])
            Z[k]=0;
        else
            if (k>R)
            {
                Z[k]=1;
                while (S[k+Z[k]]==S[1+Z[k]])
                    {
                        Z[k]++;
                        if(Z[k]==n)
                            nrrez++;
                    }
                L=k;
                R=k+Z[k]-1;
            }
            else
            {
                kp=k-(L-1);
                beta=R-(k-1);
                Z[k]=min(Z[kp],beta);
                while (S[k+Z[k]]==S[1+Z[k]])
                    {
                        Z[k]++;
                        if(Z[k]==n)
                            nrrez++;
                    }
                if (k+Z[k]-1>R)
                {
                    L=k;
                    R=k+Z[k]-1;
                }
            }
}

int main()
{
    fin>>S+1;
    n=strlen(S+1);
    strcat(S+1,"$");
    fin>>T;
    strcat(S+1,T);
    m=strlen(S+1);
    calcul(m,S,Z);
    fout<<nrrez<<"\n";
    if(nrrez>1000)
        m=n+2+1000;
    for(int i=n;i<=m;i++)
    {
        if(Z[i]==n)
            fout<<i-n-2<<" ";
    }
    fin.close();
    fout.close();
    return 0;
}