પેલિન્ડ્રોમ સબસ્ટ્રિંગ ક્વેરીઝ


મુશ્કેલી સ્તર હાર્ડ
વારંવાર પૂછવામાં આવે છે એમેઝોન ByteDance ઇબે એક્સપેડિયા Google વધુ વધુ માઈક્રોસોફ્ટ પેપાલ Pinterest સારાંશ
ડાયનેમિક પ્રોગ્રામિંગ હેશિંગ ક્વેરી સમસ્યા શબ્દમાળા

સમસ્યા નિવેદન

"પાલિન્ડ્રોમ સબસ્ટ્રિંગ ક્વેરીઝ" સમસ્યા જણાવે છે કે તમને એક શબ્દમાળા અને કેટલીક પ્રશ્નો આપવામાં આવે છે. તે ક્વેરીઝ સાથે, તમારે તે નક્કી કરવું પડશે કે તે ક્વેરીમાંથી બનાવેલ સબસ્ટ્રિંગ પેલિંડ્રોમ છે કે નહીં.

ઉદાહરણ

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] પેલિંડ્રોમ છે, અને તેથી પરિણામ હા છે. સબસ્ટ્રિંગ "અબ્બાબા" છે.

અભિગમ

અમે દરેક ક્વેરીના આધારે સ્ટ્રિંગ અને કેટલીક ક્વેરીઝ આપી છે. આપણે રચિત સબસ્ટ્રિંગ નક્કી કરવું પડશે એ પેલિન્ડ્રોમ અથવા નહીં. શબ્દમાળા વાપરો હેશિંગ આ હલ કરવા માટે. આપણે બે એરેનો ઉપયોગ કરીશું એક મૂળ શબ્દમાળા માટે અને એક ઉલટાવી સ્ટ્રિંગ માટે. તો પછી આપણે શબ્દમાળાનાં હેશ વેલ્યુ સંગ્રહિત કરીશું. અહીં હેશ મૂલ્ય એક બીજાથી અલગ હોઈ શકે છે. ધારો કે આપણે શબ્દમાળા માટે હેશ મૂલ્ય લઈ રહ્યા છીએ [] અને વિપરીત શબ્દમાળા માટે forલટું હેશ મૂલ્ય. અમે ઉપસર્ગ અને પ્રત્યય એરે લઈશું.

માની લો કે આપણી પાસે શબ્દમાળા str: "aabbbabaaa" છે.

આપણે સ્ટ્ર્ડના હેશ વેલ્યુ સ્ટોર કરીશું

ઉપસર્ગ [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.

 

તેથી હવે, તમારામાંથી ઘણા વિચારી રહ્યાં છે કે આ પ્રકારની રીતે હેશ મૂલ્યો સ્ટોર કરવાની આ રીત શા માટે છે. જવાબ એ છે કે ઓછામાં ઓછા સમયની જટિલતામાં સરળ સૂત્રનો ઉપયોગ કરીને કોઈપણ સબસ્ટ્રિંગ્સના હેશ મૂલ્યને શોધવાની રીત છે.

હેશ મૂલ્ય (ડાબે, જમણે) = ઉપસર્ગ [અધિકાર + 1] - ઉપસર્ગ [ડાબે].

ડાબી અને જમણી બાજુના પ્રારંભિક બિંદુ હોઈ શકે છે, જો આપણે શબ્દમાળા (2, 4) = "બીબીબી" ની હેશ વેલ્યુ શોધવા માંગતા હો, તો ખાલી તે હશે:

ઉપસર્ગ [5] - ઉપસર્ગ [2] = 98 * 1013 + 98 * 1014 + 98 * 1015.

આ મૂલ્ય પેલિન્ડ્રોમ શોધવા માટે મદદ કરશે. કારણ કે તે જ આપણે પ્રત્યય એરે સાથે કરીશું, પરંતુ આ વખતે છેલ્લાથી, ચાલો જોઈએ કે કેવી રીતે.

શબ્દમાળા શબ્દ: "અબ્બાબાબાઆ".

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-Left] - પ્રત્યય [n-અધિકાર -1].

ઉદાહરણ

ઉદાહરણ તરીકે: શબ્દમાળા str: "aabbbababaaa".

વિપરીત હેશ મૂલ્ય: સબસ્ટ્રિંગ (2,4):

“બીબીબીએ” ની વેલ્યુ બદલી એ “એબીબીબી” છે

પ્રત્યય [11-1] - પ્રત્યય [11-4-1] = પ્રત્યય [10] -સુફિક્સ [6].

અને હવે આપણી પાસે પેલિન્ડ્રોમ અસ્તિત્વમાં છે કે નહીં તે શોધવાનું એક સમીકરણ છે.

હવે આપણે ઉપસર્ગ અને પ્રત્યય તરીકે બે એરે લઈ રહ્યા છીએ, આપણી વચ્ચે એક સબંધ છે.

(ઉપસર્ગ [અધિકાર + 1] - ઉપસર્ગ [ડાબે])  =  (પ્રત્યય [n - ડાબે] - પ્રત્યય [n - અધિકાર- 1])

(101ડાબે) (101n - અધિકાર - 1)

 

પેલિન્ડ્રોમ સબસ્ટ્રિંગ ક્વેરીઝ

કોડ

પેલિન્ડ્રોમ સબસ્ટ્રિંગ ક્વેરીઝ માટે સી ++ કોડ

#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

પાલિન્ડ્રોમ સબસ્ટ્રિંગ ક્વેરીઝ માટે જાવા કોડ

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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન + ક્યૂ) જ્યાં “એન” શબ્દમાળા નું કદ છે અને "પ્ર" કરવા માટેના પ્રશ્નોની સંખ્યા છે. તેથી, alલ્ગોરિધમમાં રેખીય સમયની જટિલતા હોય છે, કેમ કે આપણે O (1) સમયમાં દરેક ક્વેરીનો જવાબ આપીએ છીએ.

અવકાશ જટિલતા

ઓ (એન) જ્યાં “એન” આપેલ શબ્દમાળાના અક્ષરોની સંખ્યા છે. કારણ કે આપણે શબ્દમાળા માટે હેશ વેલ્યુ સંગ્રહિત કરી છે. અમે વધારાની જગ્યાનો ઉપયોગ કર્યો.