Cod sursa(job #2217314)

Utilizator nurof3nCioc Alex-Andrei nurof3n Data 29 iunie 2018 23:14:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <fstream>

using namespace std;

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

const int DIM = 2000001;
char text[DIM * 2];
int P, lg;
int Z[DIM * 2], ap[1001], nrap;
//Z[k] reprezinta cea mai lunga secv care incepe la text[k] si este in acelasi timp prefix al lui text
void z_algorithm(char *text, int P, int lg)
{
//pt fiecare k calculam capetele L si R ale secventei a.i. aceasta sa respecte conditia de matching cu prefixul de aceeasi lungime si sa aiba R maxim
    int L = 0, R = 0;
    Z[0] = lg;
    for(int k = 1; k < lg; k++)
    {
        if(k > R)
        {
            int i;
            for(i = 0; i + k < lg && text[i] == text[i + k]; i++);
            Z[k] = i;
            if(Z[k])
            {
                L = k;
                R = k + Z[k] - 1;
            }
        }
        else if(k <= R)
        {
            int A = R - L + 1, B = R - k + 1, k2 = k - L;
            if(Z[k2] < B) ///L si R raman aceleasi
                Z[k] = Z[k2];
            else
            {
                int i;
                for(i = B; i + k < lg && text[i] == text[i + k]; i++);
                Z[k] = i;
                L = k;
                R = k + Z[k] - 1;
            }
        }
        if(k >= P && Z[k] >= P)
        {
            nrap++;
            if(nrap <= 1000)
                ap[nrap] = k - P;
        }
    }
}
int main()
{
    in.getline(text, DIM);
    P = in.gcount() - 1;
    in.getline(text + P, DIM);
    lg = P + in.gcount() - 1;
//am unit sirurile pattern + text
    if(P * 2 > lg)
    {
        out << 0;
        return 0;
    }
    z_algorithm(text, P, lg);
    out << nrap << '\n';
    for(int i = 1; i <= nrap && i <= 1000; i++)
        out << ap[i] << ' ';

    return 0;
}