استعلامات سلسلة فرعية Palindrome  


مستوى الصعوبة الثابت
كثيرا ما يطلب في أمازون ByteDance يباي اكسبيديا جوجل يستشعر Microsoft Paypal Pinterest سينوبسيس
البرمجة الديناميكية تجزئة مشكلة الاستعلام خيط

المشكلة بيان  

تنص مشكلة "استعلامات سلسلة فرعية Palindrome" على أنه تم إعطاؤك سلسلة وبعض الاستعلامات. باستخدام هذه الاستعلامات ، يجب عليك تحديد ما إذا كانت السلسلة الفرعية المكونة من هذا الاستعلام متطابقة أم لا.

مثال  

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،XNUMX] متناظرة ، وبالتالي فإن النتيجة هي نعم. السلسلة الفرعية هي "abbabba".

الرسالة  

لقد قدمنا ​​سلسلة وبعض الاستعلامات ، بناءً على كل استعلام. علينا تحديد السلسلة الفرعية التي تم تشكيلها بحيث تكون a سياق متناظر أم لا. استخدم String تجزئة لحل هذا. سنستخدم مصفوفتين واحدة للسلسلة الأصلية وواحدة للسلسلة المعكوسة. ثم سنقوم بتخزين قيم تجزئة السلسلة. هنا يمكن أن تكون قيمة التجزئة مختلفة عن بعضها البعض. لنفترض أننا نأخذ قيمة التجزئة للسلسلة [] وقيمة التجزئة العكسية للسلسلة المعكوسة. سنأخذ مصفوفات البادئة واللاحقة.

لنفترض أن لدينا شارع سلسلة: "aabbbababaaa".

سنقوم بتخزين قيم التجزئة لـ str as

بادئة [i] = str [0] + str [1] * 101 + str [2] * 1012  + ………. + str [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.

 

انظر أيضا
الحد الأدنى من الوقت لزيارة جميع النقاط حل Leetcode

حتى الآن ، يفكر الكثير منكم في سبب كون هذه هي طريقة تخزين قيم التجزئة بهذه الطريقة من هذا النوع. الإجابة هي طريقة البحث عن أي قيمة تجزئة لسلسلة فرعية معينة باستخدام صيغة بسيطة بأقل تعقيد زمني.

قيمة التجزئة (يسار ، يمين) = بادئة [يمين + 1] - بادئة [يسار].

يمكن أن يكون اليسار واليمين نقطة بداية فرعية ، إذا أردنا العثور على قيمة التجزئة للسلسلة (2 ، 4) = "bbb" ، فستكون ببساطة:

البادئة [5] - البادئة [2] = 98 * 1013 + 98 * 1014 + 98 * 1015.

هذه القيمة ستساعد في اكتشاف التناظر. لأن نفس الشيء سنفعله مع مصفوفة اللاحقة ، لكن هذه المرة من الماضي ، دعنا نرى كيف.

سلسلة السلسلة: "aabbababaaa".

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.

الآن يمكننا حساب قيمة قيمة التجزئة العكسية باستخدام:

قيمة التجزئة العكسية (يسار ، يمين): قيمة التجزئة (يمين ، يسار) = لاحقة [n-يسار] - لاحقة [n-Right-1].

مثال

على سبيل المثال: String str: “aabbbababaaa”.

قيمة التجزئة العكسية: السلسلة الفرعية (2,4،XNUMX):

عكس قيمة "bbba" هو "abbb"

اللاحقة [11-1] - اللاحقة [11-4-1] = لاحقة [10] - غلاف [6].

والآن لدينا معادلة لاكتشاف التناظر إذا كان موجودًا.

الآن لدينا مصفوفتان كبادئة ولاحقة ، لدينا علاقة بينهما.

(بادئة [يمين + 1] - بادئة [يسار])  =  (لاحقة [n - يسار] - لاحقة [n - يمين- 1])

انظر أيضا
كم عدد الأرقام أصغر من حل Leetcode الرقم الحالي

(101اليسار) (101ن - حق - 1)

 

استعلامات سلسلة فرعية Palindromeدبوس  

رمز  

كود C ++ لاستعلامات سلسلة Palindrome الفرعية

#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

كود جافا لاستعلامات سلسلة Palindrome الفرعية

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

تحليل التعقيد  

تعقيد الوقت

يا (N + Q) أين "N" هو حجم السلسلة و "س" هو عدد الاستعلامات المطلوب تنفيذها. لذلك ، فإن الخوارزمية لها تعقيد زمني خطي ، حيث نجيب على كل استفسار في وقت O (1).

انظر أيضا
ابحث عن المصفوفة الفرعية بمجموع معين (مقابض الأرقام السالبة)

تعقيد الفضاء

على) أين "N" هو عدد الأحرف في السلسلة المحددة. لأننا قمنا بتخزين قيم التجزئة للسلسلة. استخدمنا مساحة إضافية.