Îl cunoașteți pe Dorel cel ”priceput” la toate. Acesta și-a propus să ”strice” armonia unui șir S format din N caractere litere mică ale alfabetului englez, S=(S[1],S[2],…,S[N]).

El alege la întâmplare un caracter din șir, caracter aflat pe poziția k (1≤k≤N) și caută în stânga lui k primul caracter mai mare sau egal cu S[k], fie acesta aflat pe poziția i, S[k]≤S[i]. Dacă acesta nu există, i=1. Această alegere nu este suficientă. Dorel caută în dreapta lui k primul caracter mai mic sau egal cu S[k], fie acesta pe poziția j, S[j]≤S[k]. Dacă acesta nu există, j=N. Extrage din șirul S subșirul astfel delimitat. Ca urmare a alegerii făcute, Dorel obține două subșiruri:

X=(S[1],S[2],…,S[i-1],S[j+1],S[j+2],…,S[N])
Y=(S[i],S[i+1],…,S[j])

Cerința

Cunoscând șirul S, ajutați-l pe Dorel să răspundă la Q întrebări de forma:

Pentru o poziție k din șirul S să se determine lungimea maximă a unei subsecvențe palindromice comune șirurilor X și Y.

Date de intrare

Fișierul de intrare dorel.in conține pe prima linie pe prima linie un șir de caractere. Pe cea de-a doua linie o valoare naturală nenulă Q. Pe următoarea linie cele Q întrebări în formatul precizat în enunț.

Date de ieșire

Fișierul de ieșire dorel.out va conține pe prima linie răspunsurile la cele Q întrebări, separate prin câte un spațiu.

Restricții și precizări

1 ≤ N ≤ 10000
1 ≤ Q ≤ 5000
N * Q ≤ 5000000
X și Y sunt șiruri nevide
prin subsecvență palindromică a unui șir înțelegem o succesiune de caractere aflate pe poziții consecutive în șir care este palindrom (subsecvența parcursă de la stânga la dreapta este identică cu secvența parcursă de la dreapta la stânga).
lungimea maximă a unei subsecvențe palindromice comune ≤ 1000

Exemplu

dorel.in

xexxxdexxexaegf
4
6 8 15 3

dorel.out

4 2 0 3

Explicație

Răspunsul la cele 4 întrebări

X=”xexxegf”, Y=”xdexxexa”.
Subsecvența palindromică comună =”exxe” având lungimea =4

X=”xexxexaegf”, Y=”xdexx”
Subsecvența palindromică comună =”xx” având lungimea =2

X=”xexxxdexxexae”, Y=”gf”
Subsecvența palindromică comună =”” având lungimea =0

X=”xdexxexaegf”, Y=”xexx”
Subsecvența palindromică comună =”xex” având lungimea =3

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Dorel:

/*
   prof. Eugen Nodea
   Complexitate: O(Q*N*log(N))
*/
# include <bits/stdc++.h>
# define NMax 100005
# define sigma 30
using namespace std;

ifstream f("dorel.in");
ofstream g("dorel.out");

int i, j, n, m, st, dr, mij, Q, poz, ST, DR, NN, LX, LY, ok;
int sol, SOL;
int pi[NMax], X[NMax], Y[NMax], Lpar[NMax], Limpar[NMax], v[2*NMax], P[2*NMax];
int minn[sigma], maxx[sigma], stMax[NMax], drMin[NMax], solutie[NMax];
char s[NMax];

void preprocesare() ///preprocesez maxim, respectiv minim
{
    int x;
    for (int i=1; i<=n; ++i) { ///stanga
        int CH = s[i] - 'a' + 1;
        x = 1;
        for (int j=CH; j<=sigma; ++j)
            x = max(x, maxx[j]);
        stMax[i] = x; maxx[CH] = i;
    }

    for (int i=n; i>=1; --i) { ///dreapta
        int CH = s[i] - 'a' + 1;
        x = n;
        for (int j=CH; j>=1; --j)
            if (minn[j] != 0) x = min(x, minn[j]);
        drMin[i] = x; minn[CH] = i;
    }
}
void manacher() /// complexitate O(n)
{
    int st = 0, dr = 0, mid = 0;
    for (i=1; i<=n; ++i) {
        v[++NN] = '$';
        v[++NN] = s[i];
    }
    v[++NN] = '$';
    for (i=1; i<=NN; ++i) {
        if (dr < i) {
            st = dr = i;
            P[i] = 1; mid = i;
            while (1<st && dr<NN && v[st-1] == v[dr+1]) {
                ++P[i];
                --st; ++dr;
            }
        } else {
            int poz = mid - (i-mid);
            if (poz - P[poz] + 1 == st) {
                P[i] = P[poz]; mid = i;
                st = i - (dr-i);
                while (1<st && dr<NN && v[st-1] == v[dr+1]) {
                    ++P[i];
                    --st; ++dr;
                }
            } else P[i] = min(P[poz], dr - i + 1);
        }
    }
    int np = 0, ni = 0;
    for (int i=2; i<NN; ++i) {
        if (v[i]=='$') Lpar[++np]  = P[i] / 2;
                  else Limpar[++ni]= P[i] / 2;
    }
}
void make_aux(int st, int dr)
{
    LX = 0;
    for (int i=1; i<=n; ++i)
        if (i<st || dr<i) X[++LX] = s[i];
}
bool verif(int st, int dr) /// verificare subsecventa comuna
{
    int k = 0; LY = 0;
    for (int i=st; i<=dr; ++i) Y[++LY] = s[i]; /// extrag Y

    for (int i=2; i<=LY; ++i) {
        while (k && Y[k+1] != Y[i])
            k = pi[k];
        if (Y[k+1] == Y[i]) ++k;
        pi[i] = k;
    }
    k = 0;
    for (int i=1; i<=LX; ++i) {
        while (k && Y[k+1] != X[i])
            k = pi[k];
        if (Y[k+1] == X[i]) ++k;
        if (k == LY) return 1;
    }

    return 0;
}
int main()
{
    f.getline (s+1, NMax); n = strlen(s+1);

    preprocesare (); manacher ();

    f >> Q;
    for (int q=1; q<=Q; ++q) {
        f >> poz;
        ST = stMax[poz]; DR = drMin[poz];
        SOL = 0;
        if (solutie[poz]) {
            g << solutie[poz] << " ";
            continue;
        }

        make_aux(ST, DR); /// extrag subsirul Y, construiesc X

        ///caut binar lungimea maxima a unui palindrom
        st = 1; dr = (DR-ST+1) / 2; sol = 0; ///impar
        if ((DR - ST + 1) % 2 == 1) ++dr;
        while (st <= dr) {
            mij = (st + dr) / 2; ok = 0;
            for (int i=ST+mij-1; i<=DR-mij+ 1; ++i) ///mijlocul
                if (Limpar[i] >= mij && verif(i-mij+1, i+mij-1)){
                    ok=1;
                    break;
                }

            if (ok) st = mij+1, sol = mij;
               else dr = mij-1;
        }

        SOL = max(SOL, 2*sol - 1);

        st = 1; dr = (DR-ST+1) / 2; sol = 0; ///par
        while (st <= dr) {
            mij = (st + dr) / 2; ok = 0;
            for (int i=ST+mij-1; i<=DR-mij; ++i) //mijlocul
                if (Lpar[i] >= mij && verif(i-mij+1, i+mij)){
                    ok=1;
                    break;
                }
            if (ok) st = mij+1, sol = mij;
               else dr = mij-1;
        }
        SOL = max(SOL, 2*sol);
        solutie[poz] = SOL;

        g << solutie[poz] << " ";
    }
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1729 Dorel

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1729 Dorel de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1729 Dorel