Palindrome Substring հարցումներ


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են Amazon ByteDance eBay Expedia Google Intuit Microsoft PayPal Pinterest Սինոփսիս
Դինամիկ ծրագրավորում Հեշինգ Հարցման խնդիր String

Խնդիրի հայտարարություն

«Palindrome Substring Հարցումներ» խնդրում նշվում է, որ ձեզ տրվում է String և որոշ հարցումներ: Այդ հարցումների միջոցով դուք պետք է որոշեք ՝ արդյոք այդ հարցումից կազմված ենթալարը պալինդրոմ է, թե ոչ:

Օրինակ

String str = "aaabbabbaaa"

Queries q[] = { {2, 3}, {2, 8},{5, 7}, {3, 7} }
The Substring [2 3] is not a palindrome

The Substring [2 8] is a palindrome

The Substring [5 7] is not a palindrome

The Substring [3 7] is a palindrome

Բացատրություն. [2,8] ենթալարը պալինդրոմ է, ուստի արդյունքն ԱՅՈ է: Ենթաշարը «abbabba» է:

Մոտեցում

Մենք տվել ենք String և որոշ հարցումներ ՝ յուրաքանչյուր հարցման հիման վրա: Մենք պետք է որոշենք, որ այսպես կազմավորված ենթալարը ա պալինդրոմ կամ ոչ. Օգտագործեք տողը Հեշինգ սա լուծելու համար: Մենք պատրաստվում ենք օգտագործել երկու զանգված `մեկը սկզբնական տողի, և մեկը` հակառակ տողի համար: Դրանից հետո մենք կպահպանենք String- ի հեշ արժեքները: Այստեղ Hash արժեքը կարող է տարբերվել մեկը մյուսից: Ենթադրենք, որ String- ի համար վերցնում ենք Hash արժեքը և հակառակ String- ի համար հակադարձ Hash արժեքը: Մենք վերցնելու ենք նախածանցի և ածանցի զանգվածներ:

Ենթադրենք, որ մենք ունենք String str. «Aabbbababaaa»:

Մենք պահելու ենք str- ի հեշ արժեքները

Նախածանց [i] = str [0] + str [1] * 101 + փող [2] * 1012  + ………. + Փող [i-1] * 101 *i-1  .

[I] նախածանցի յուրաքանչյուր արժեքի համար: Մենք կունենանք հետևյալ արժեքները.

Prefix[0]=0,
Prefix[1]= 97 + 97 *101, ( 0+ ASCII value of a)
Prefix[2]= 97 + 97 *101 + 98 *101^2
Prefix[3]= 97 + 97 *101 + 98 *101^2 + 98 *101^3 ( 0 + ASCII value of a’s and ASCII value of b).
.
.
.
Prefix [12]= 97 + 97 *101 + 98 *101^2 + 98 *101^3 +…… +97 *101^11 as length of String is 12.

 

Այսպիսով, հիմա ձեզանից շատերը մտածում են, թե ինչու է սա Hash արժեքները այս տեսակի նման պահելու միջոց: Պատասխանը ցանկացած տրված ենթաշարքի հեշ արժեքը որոնելու միջոց է `օգտագործելով պարզ բանաձև նվազագույն ժամանակի բարդության մեջ:

Հաշի արժեք (Ձախ, Աջ) = նախածանց [Աջ + 1] - նախածանց [Ձախ]:

Ձախն ու աջը կարող են ենթակայության սկզբնական կետ լինել, Եթե մենք ուզում ենք գտնել տողի հեշ արժեքը (2, 4) = «bbb», ապա դա կլինի հետևյալը.

նախածանց [5] - նախածանց [2] = 98 * 1013 + 98 * 1014 + 98 * 1015.

Այս արժեքը կօգնի պարզել պալինդրոմը: Քանի որ նույնը մենք կանենք զանգվածի ածանցի հետ, բայց այս անգամ վերջինից, եկեք տեսնենք, թե ինչպես:

Լարի փող. «Aabbbababaaa»:

suffix[i] = str[n-1]+ str[n-2] *101 + str[n-3]*1022  + ……….+ str[n-i]*101*i-1  .
suffix[0]=0,
suffix [1]= 97 + 97 *101, ( 0+ ASCII value of a)
suffix [2]= 97 + 97 *101 + 97 *101^2,
suffix [3]= 97 + 97 *101 + 97 *101^2 + 98 *101^3 ( 0 + ASCII value of a’s and ASCII value of b).
.
.
.
.
suffix [11]= 97 + 97 *101 + 97 *101^2 + 98 *101^3 +…… +97 *101^10 as length of String is 11.

Այժմ մենք կարող ենք հաշվարկել հակառակ Hash արժեքի արժեքը ՝ օգտագործելով.

Հակադարձ հեշ արժեք (ձախ, աջ). Հեշ արժեք (աջ, ձախ) = վերջածանց [n- ձախ] - վերջածանց [n- աջ -1]:

Օրինակ

Օրինակ ՝ Լարի փող. «Aabbbababaaa»:

Հակադարձ հեշ արժեք. Ենթաշարք (2,4):

«Bbba» - ի արժեքը փոխելը «abbb» է

Ածանց [11-1] - վերջածանց [11-4-1] = ածանց [10] -վավերադասություն [6]:

Եվ հիմա մենք ունենք հավասարում պալինդրոմը գոյություն ունենալու մասին պարզելու համար:

Այժմ մենք ունենք երկու զանգված որպես նախածանց և վերջածանց, նրանց միջև կապ կա:

(նախածանց [Աջ + 1] - նախածանց [Ձախ])  =  (վերջածանց [n - Ձախ] - վերջածանց [n - աջ - 1])

(101Left) (101n - --իշտ - 1)

 

Palindrome Substring հարցումներ

Կոդ

C ++ կոդ Palindrome Substring հարցումների համար

#include<iostream>

using namespace std;

#define p 101
#define MOD 1000000007

struct Queries
{
    int left, right;
};
bool CheckPalindrome(string str, int left, int right)
{
    while (right > left)
        if (str[left++] != str[right--])
            return (false);
    return (true);
}
unsigned long long int moduloPower(unsigned long long int base,unsigned long long int exponent)
{
    if (exponent == 0)
        return 1;
    if (exponent == 1)
        return base;

    unsigned long long int temp = moduloPower(base, exponent / 2);

    if (exponent % 2 == 0)
        return (temp % MOD * temp % MOD) % MOD;
    else
        return (((temp % MOD * temp % MOD) % MOD)* base % MOD)% MOD;
}

unsigned long long int ModuloMultiplicativeInverse(unsigned long long int n)
{
    return moduloPower(n, MOD - 2);
}

void HashPrefix( string str, int n, unsigned long long int prefix[], unsigned long long int powerArr[])
{
    prefix[0] = 0;
    prefix[1] = str[0];

    for (int i = 2; i <= n; i++)
        prefix[i] = (prefix[i - 1] % MOD + (str[i - 1] % MOD * powerArr[i - 1] % MOD) % MOD) % MOD;

    return;
}

void HashSuffix( string str, int n, unsigned long long int suffix[], unsigned long long int powerArr[])
{
    suffix[0] = 0;
    suffix[1] = str[n - 1];

    for (int i = n - 2, j = 2; i >= 0 && j <= n; i--, j++)
        suffix[j] = (suffix[j - 1] % MOD+ (str[i] % MOD* powerArr[j - 1] % MOD)% MOD)% MOD;

    return;
}
void GetQueryOutput(string str, Queries q[], int m, int n, unsigned long long int prefix[], unsigned long long int suffix[], unsigned long long int powerArr[])
{
    for (int i = 0; i <= m - 1; i++)
    {
        int left = q[i].left;
        int right = q[i].right;

        unsigned long long HashValue= ((prefix[right + 1] - prefix[left] + MOD) % MOD* ModuloMultiplicativeInverse(powerArr[left]) % MOD)% MOD;

        unsigned long long reverseHashValue= ((suffix[n - left] - suffix[n - right - 1] + MOD) % MOD* ModuloMultiplicativeInverse(powerArr[n - right - 1]) % MOD)% MOD;

        if (HashValue == reverseHashValue)
        {
            if (CheckPalindrome(str, left, right) == true)
                cout<<"The Substring ["<< left <<" "<<right<<"] is a palindrome\n";
            else
                cout<<"The Substring ["<< left <<" "<<right<<"] is a palindrome\n";
        }

        else
            cout<<"The Substring ["<< left <<" "<<right<<"] is not a palindrome\n";
    }

    return;
}
void assginedPowers(unsigned long long int powerArr[], int n)
{
    powerArr[0] = 1;

    for (int i = 1; i <= n; i++)
        powerArr[i] = (powerArr[i - 1] % MOD * p % MOD) % MOD;

    return;
}
int main()
{
    string str = "aaabbabbaaa";
    int n = str.length();

    unsigned long long int powerArr[n + 1];

    assginedPowers(powerArr, n);

    unsigned long long int prefix[n + 1];
    unsigned long long int suffix[n + 1];

    HashPrefix(str, n, prefix, powerArr);
    HashSuffix(str, n, suffix, powerArr);

    Queries q[] = { {2, 3}, {2, 8},{5, 7}, {3, 7} };
    int m = sizeof(q) / sizeof(q[0]);

    GetQueryOutput(str, q, m, n, prefix, suffix, powerArr);
    return (0);
}
The Substring [2 3] is not a palindrome
The Substring [2 8] is a palindrome
The Substring [5 7] is not a palindrome
The Substring [3 7] is a palindrome

Java կոդ Palindrome Substring հարցումների համար

public class PalindromeSubstringQuery
{
    static int p = 101;
    static int MOD = 1000000007;

    public static class Queries
    {
        int left, right;
        public Queries(int left, int right)
        {
            this.left = left;
            this.right = right;
        }
    }
    public static boolean CheckPalindrome(String str, int left, int right)
    {
        while (right > left)
        {
            if (str.charAt(left++) != str.charAt(right--))
                return (false);
        }
        return (true);
    }
    public static int moduloPower(int base, int exponent)
    {
        if (exponent == 0)
        {
            return 1;
        }
        if (exponent == 1)
        {
            return base;
        }
        int temp = moduloPower(base, exponent / 2);

        if (exponent % 2 == 0)
        {
            return (temp % MOD * temp % MOD) % MOD;
        }
        else
        {
            return (((temp % MOD * temp % MOD) % MOD) * base % MOD) % MOD;
        }
    }
    public static int ModuloMultiplicativeInverse(int n)
    {
        return moduloPower(n, MOD - 2);
    }

    public static void HashPrefix(String str, int n,int prefix[], int powerArr[])
    {
        prefix[0] = 0;
        prefix[1] = str.charAt(0);

        for (int i = 2; i <= n; i++)
        {
            prefix[i] = (prefix[i - 1] % MOD+ (str.charAt(i - 1) % MOD * powerArr[i - 1] % MOD) % MOD) % MOD;
        }
        return;
    }
    public static void HashSuffix(String str, int n,int suffix[], int powerArr[])
    {
        suffix[0] = 0;
        suffix[1] = str.charAt(n - 1);

        for (int i = n - 2, j = 2; i >= 0 && j <= n; i--, j++)
        {
            suffix[j] = (suffix[j - 1] % MOD + (str.charAt(i) % MOD* powerArr[j - 1] % MOD) 	% MOD) % MOD;
        }
        return;
    }
    public static void GetQueryOutput( String str, Queries q[], int m, int n, int prefix[], int suffix[], int powerArr[])
    {
        for (int i = 0; i <= m - 1; i++)
        {
            int left = q[i].left;
            int right = q[i].right;

            long HashValue= ((prefix[right + 1] - prefix[left] + MOD) % MOD* ModuloMultiplicativeInverse(powerArr[left]) % MOD)% MOD;

            long reverseHashValue= ((suffix[n - left] - suffix[n - right - 1] + MOD) % MOD* ModuloMultiplicativeInverse(powerArr[n - right - 1]) % MOD)% MOD;

            if (HashValue == reverseHashValue)
            {
                if (CheckPalindrome(str, left, right) == true)
                {
                    System.out.print("The Substring ["+left+" "+ right+"] is a palindrome\n");
                }
                else
                {
                    System.out.print("The Substring ["+left+" "+ right+"] is not a palindrome\n");
                }
            }
            else
            {
                System.out.print("The Substring ["+left+" "+ right+"] is not a palindrome\n");
            }
        }
        return;
    }
    public static void assginedPowers(int powerArr[], int n)
    {
        powerArr[0] = 1;

        for (int i = 1; i <= n; i++)
            powerArr[i] = (powerArr[i - 1] % MOD * p % MOD) % MOD;

        return;
    }
    public static void main(String[] args)
    {
        String str = "aaabbabbaaa";
        int n = str.length();

        int[] powerArr = new int[n + 1];

        assginedPowers(powerArr, n);

        int[] prefix = new int[n + 1];
        int[] suffix = new int[n + 1];

        HashPrefix(str, n, prefix, powerArr);
        HashSuffix(str, n, suffix, powerArr);

        Queries q[] = { new Queries(2, 3), new Queries(2, 8),new Queries(5, 7), new Queries(3, 7) };

        int m = q.length;

        GetQueryOutput(str, q, m, n, prefix, suffix, powerArr);
    }
}
The Substring [2 3] is not a palindrome
The Substring [2 8] is a palindrome
The Substring [5 7] is not a palindrome
The Substring [3 7] is a palindrome

Բարդության վերլուծություն

Timeամանակի բարդություն

O (N + Q) որտեղ «Ն» լարի չափն է և «Ք» կատարվող հարցումների քանակն է: Այսպիսով, ալգորիթմը ունի գծային ժամանակի բարդություն, քանի որ յուրաքանչյուր հարցումին մենք պատասխանում ենք O (1) ժամանակով:

Տիեզերական բարդություն

ՎՐԱ) որտեղ «Ն» տրված տողի նիշերի թիվն է: Քանի որ լարայինի համար մենք պահպանել ենք hash արժեքներ: Մենք լրացուցիչ տարածք օգտագործեցինք: