C++-ի օրական բիթ(ե) | Ամենաերկար պալինդրոմային ենթաշարը

C++ #198-ի ամենօրյա բիթ(ե), Ընդհանուր հարցազրույցի խնդիր. Ամենաերկար պալինդրոմային ենթատող:

Այսօր մենք կանդրադառնանք հարցազրույցի ընդհանուր խնդրին. Ամենաերկար palindromic substring.

Ստանալով տողը որպես std::string_view, վերադարձրեք ամենաերկար palindromic ենթատողը (եթե բազմապատիկ, ապա առաջինը):

Վերոնշյալ օրինակում ամենամեծ պալինդրոմային ենթաշարը «բաբ» է:

Նախքան լուծումը կարդալը շարունակելը, ես խրախուսում եմ ձեզ փորձել ինքներդ լուծել այն: Ահա Compiler Explorer-ի հղումը մի քանի փորձարկման դեպքերով. https://compiler-explorer.com/z/fKT5MzoGE:

Լուծում

Կտրուկ ուժի լուծումը (ստուգելով յուրաքանչյուր ենթալարի պալինդրոմի համար) կվերցնի O(n³): Մենք կարող ենք ավելի լավ անել:

Առաջին բարելավումը պալինդրոմների բնորոշ համաչափությունից օգտվելն է: Պալինդրոմներն ընդարձակվում են իրենց կենտրոնից, որը մենք կարող ենք ընդօրինակել մեր որոնման մեջ: Մենք ընդլայնվում ենք յուրաքանչյուր պոտենցիալ կենտրոնից մինչև չհանդիպենք երկու նիշերի, որոնք չեն համընկնում: Հիշեք, որ կենտրոնը կարող է լինել կերպար կամ երկու նիշերի միջև եղած բացը: Մենք կարող ենք ի վերջո կատարել O(n) համեմատություններ յուրաքանչյուր կենտրոնի համար, ինչը հանգեցնում է O(n²) ընդհանուր բարդության:

std::string_view longest_palindrome(std::string_view s) {
    int64_t left = 0;
    int64_t len = 0;

    // For every centre:
    for (int64_t c = 0; c < std::ssize(s); ++c) {
        // The centre is a character:
        for (int64_t i = c, j = c; 
             i >= 0 && j < std::ssize(s) && s[i] == s[j];
             --i,++j) {
            if (j-i+1 > len) { // Update max
                left = i;
                len = j-i+1;
            }
        }
        // The centre is in between characters:
        for (int64_t i = c, j = c+1;
             i >= 0 && j < std::ssize(s) && s[i] == s[j];
             --i,++j) {
            if (j-i+1 > len) { // Update max
                left = i;
                len = j-i+1;
            }
        }
    }
    return s.substr(left, len);
}

Բացեք լուծումը Compiler Explorer-ում:

Թեև վերը նշված մոտեցումը միանգամայն վավեր է, մենք կարող ենք փրկել որոշ խնդիրներ և մի քանի նիշ՝ կիրառելով տեսակետներ և ալգորիթմներ խնդրին:

#include <ranges>

std::string_view longest_palindrome_2(std::string_view s) {
    std::string_view result;

    for (int64_t c = 0; c < std::ssize(s); ++c) {
        auto left = s | std::views::take(c) | std::views::reverse;

        // Even sized palindromes
        auto right = s | std::views::drop(c);
        auto [le,re] = std::ranges::mismatch(left,right);
        if (re-le.base() > std::ssize(result))
            result = std::string_view(le.base(), re);
        // Odd sized palindromes
        auto right_odd = s | std::views::drop(c+1);
        auto [lo,ro] = std::ranges::mismatch(left,right_odd);
        if (ro-lo.base() > std::ssize(result))
            result = std::string_view(lo.base(), ro);
    }
    return result;
}

Բացեք լուծումը Compiler Explorer-ում:

Վերոնշյալ մոտեցումներից որևէ մեկը պետք է բավարար լինի հարցազրույցի համար: Այնուամենայնիվ, կա O(n) ալգորիթմ: Եկեք մտածենք մեր մոտեցման անարդյունավետության մասին:

Ենթադրենք, մենք հենց նոր պարզեցինք, որ կենտրոնում գտնվող պալինդրոմը, որը նշանակում է սպիտակ բջիջ, ունի չորս շառավիղ (այսինքն՝ ընդհանուր երկարությունը 9), և երկու կարմիր նիշերը տարբեր են: Սովորաբար մենք կանցնեինք հաջորդ կենտրոն, բայց մենք ունենք շատ տեղեկատվություն, որը չենք օգտագործում: Քանի որ պալինդրոմը սիմետրիկ է, մենք կարող ենք նորից օգտագործել այն տեղեկատվությունը, որը մենք հաշվարկել ենք նախորդ կենտրոնների համար:

Եթե ​​նախորդ կենտրոնում ամենամեծ պալինդրոմը ամբողջությամբ պարունակվում է մեր նոր պալինդրոմում, մենք կարող ենք պատճենել այս տեղեկատվությունը, քանի որ նախորդ պալինդրոմը հայելային բովանդակության մի մասն է:

Եթե ​​նախորդ կենտրոնում գտնվող ամենամեծ պալինդրոմը դուրս է գալիս ձախ կողմում գտնվող մեր ներկայիս պալինդրոմից, մենք ունենք մի փոքր ավելի բարդ իրավիճակ: Մենք գիտենք, որ դրա մի մասն արդեն հայելային է։ Այս դեպքում դա երեք շառավղով պալինդրոմ է։ Կարո՞ղ է այս պալինդրոմը դեռ աճել: Բարեբախտաբար, դա չի կարող: Եթե ​​այն հասնի չորս չափի, դա կստիպի երկու կարմիր նիշերը նույնը լինել. սակայն, դա հակասում է մեր նախապայմաններին։

Վերջապես, եկեք դիտարկենք մի պալինդրոմ, որը ճշգրտորեն տեղավորվում է սահմանի մեջ: Սա ներկայացնում է միակ դեպքը, երբ նոր պալինդրոմը դեռ կարող է աճել, քանի որ մենք չենք կարող բացառել, որ նարնջագույն բջիջը համապատասխանում է ճիշտ կարմիր բջիջին: Այնուամենայնիվ, մենք չպետք է սկսենք զրոյից. Մենք արդեն գիտենք, որ շառավիղը առնվազն երեք է։

Դնելով վերը նշված դիտարկումները՝ մենք ի վերջո հայտնվում ենք Manacher-ի ալգորիթմի հետ, որը կարող է գտնել O(n-ում) ամենամեծ պալինդրոմային ենթատողը: Հետևյալը պարզեցված տարբերակ է, որը վերադարձնում է միայն առավելագույն պալինդրոմի չափը:

int64_t manachers(std::string_view s) {
    std::vector<int> lengths(s.length(), 0);
    int64_t radius = 0;
    int64_t c = 0;
    while (c < std::ssize(s)) {
        // Expand from the current centre until
        // we find non-matching characters
        while (c - (radius+1) >= 0 && 
               c + (radius+1) < std::ssize(s) && 
               s[c - (radius+1)] == s[c + (radius+1)])
            ++radius;
        lengths[c] = radius; // Record the radius

        int64_t curr_c = c;
        int64_t curr_r = radius;

        // Precalculate minimum radius for the next centre(s)
        ++c;
        radius = 0;
        while (c <= curr_c + curr_r) {
            int64_t mirror = curr_c - (c - curr_c);
            int64_t max_radius = curr_c + curr_r - c;

            // Completely mirrored palindrome
            if (lengths[mirror] < max_radius) {
                lengths[c] = lengths[mirror]; // Reuse
                ++c;
            // Palindrome that extends beyond current palindrome
            } else if (lengths[mirror] > max_radius) {
                lengths[c] = max_radius; // Truncate
                ++c;
            // Palindrome that fits exactly into the boundary
            } else {
                // Can expand but we know that max_radius
                // is already mirrored.
                // i.e. no point in rechecking in the while loop above
                radius = max_radius;
                break;
            }
        }
    }
    return 2*std::ranges::max(lengths)+1;
}

Բացեք լուծումը Compiler Explorer-ում:

Այնուամենայնիվ, դուք կարող եք նկատել, որ մենք ենթադրում ենք, որ մենք ունենք պալինդրոմի կենտրոն: Սա այս ալգորիթմի հիմնական բացասական կողմն է, որը կարելի է մեղմել՝ յուրաքանչյուր զույգ նիշերի միջև կեղծ նիշեր ներմուծելով: Այն, ինչ նախկինում կլիներ հավասարաչափ պալինդրոմ, այժմ կունենա նոր կենտրոն՝ կեղծ կերպարով: