Pentru un şir de caractere S, vom nota cu lmax[S] lungimea maximă a unei secvenţe palindromice conţinută în şirul S. Astfel, pentru şirul S=”abAabaabC”, lmax[S]=4, iar pentru şirul S=”a”, lmax[S]=1.

Prin secvenţa palindromică a unui şir S înţelegem un subşir de caractere aflate pe poziţii consecutive, ce formează un palindrom.

Cerința

Date fiind N şiruri de caractere S[1], S[2],…, S[n] şi o valoare naturală L, se cere să se determine numărul de secvenţe de şiruri de caractere de forma: S[i], S[i+1], … , S[j], cu i<=j, pentru care lmax[S[i]]+lmax[S[i+1]]+... +lmax[S[j]]=L.

Date de intrare

Fișierul de intrare secvpal1.in conține pe prima linie două numere naturale N, L cu semnificaţia din enunţ, iar pe fiecare dintre următoarele N linii, câte un şir de caractere.

Date de ieșire

Fișierul de ieșire secvpal1.out va conține pe prima linie un număr natural nr ce reprezintă numărul de secvenţe de şiruri de caractere ce îndeplinesc condiţia cerută.

Restricții și precizări

2 ≤ N ≤ 50 000;
0 ≤ nr ≤ 10 000;
1 ≤ lungimea maximă a oricărui şir S[i] ≤ 10 000, 1≤i≤N;
1 ≤ lungimea maximă a unei secvenţe palindromice lmax[S[i]] ≤ 1 000;
1 ≤ (lungimea maximă şir S[i]) × N ≤ 1 000 000;
Cele N şiruri de caractere conţin doar caracterele ‘A’..’Z’, ’a’..’z’;
Un palindrom este un şir de caractere care citit de la stânga la dreapta sau de la dreapta la stânga este acelaşi.

Exemplu

secvpal1.in

5 11
aCCACCACaBa
AAPAPAACCAA
acaacc
capac
CACAACAACACCAACP

secvpal1.out

Explicație

1. lmax(”aCCACCACaBa”)=6
2. lmax(”AAPAPAACCAA”)=7
3. lmax(”acaacc”)=4
4. lmax(”capac”)=5
5. lmax(”CACAACAACACCAACP”)=11

Cele două secvenţe de lungime 11 sunt: (2,3) şi (5)

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 SecvPal1:

/*
    Solutie ce determina secv. palindromica in O(Lmax^2),
    Lmax - lungimea maxima a unui sir
    optimizata 100p
    prof. Eugen Nodea
*/
# include <fstream>
# include <cstring>

using namespace std;

ifstream fin("secvpal1.in");
ofstream fout("secvpal1.out");

char s[50003],c;
int N, i, L, nr, S, j;
int a[50003];

inline int lmax(char s[])
{
    int st, dr, centru;
    int k = 0, i, p = 0;
    int Max = 0, n = strlen(s);
    //pot avea un secv. pald. de lungime para sau impara
    for(p=0; p<=1; ++p)
    {
        for(i=0; 2 * (n - i ) > Max; ++i)
        {
            //alegem centrul palindromului
            centru = i;
            st = dr = centru;   // palindrom cu nr. elem. par
            k = -1;
            if(p == 1)          // palindrom cu nr. elem. impar
            {
                ++dr;
                k = 0;
            }
            //incercam sa marim palindromul in stanga si dreapta
            while(s[st] == s[dr] && st>=0 && dr<n)
            {
                        k += 2;
                        --st; ++dr;
            }
            if(k > Max)
            {
                Max = k;
            }
        }
    }
    return Max;
}

int main()
{
    fin >> N >>L;
    fin.get();
    for (i=1; i<=N; ++i)
    {
        fin.getline(s,50003);
        a[i] = lmax(s);
    }

    i = 1; S = 0; nr = 0; j = 1;
    while (i<=N)
    {
        while (S + a[j] <= L && j<=N)
        {
            S += a[j];
            ++j;
        }
        if (S == L) nr ++;
        S = S - a[i];
        ++i;
    }
    fout << nr << "
";
    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 #713 SecvPal1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #713 SecvPal1 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 #713 SecvPal1