회문 하위 문자열 쿼리

난이도 하드
자주 묻는 질문 아마존 ByteDance 이베이 Expedia 구글 인튜이트 Microsoft 페이팔 클립 Synopsys
동적 프로그래밍 해싱 쿼리 문제 조회수 50

문제 정책

"Palindrome Substring Queries"문제는 문자열과 일부 쿼리가 제공되었음을 나타냅니다. 이러한 쿼리를 사용하여 해당 쿼리에서 형성된 하위 문자열이 회문인지 여부를 확인해야합니다.

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]은 회문이므로 결과는 YES입니다. 하위 문자열은 "abbabba"입니다.

접근

각 쿼리를 기반으로 문자열과 몇 가지 쿼리를 제공했습니다. 이렇게 형성된 부분 문자열을 결정해야합니다. 회문 또는 아닙니다. 문자열 사용 해싱 이것을 해결하기 위해. 원래 문자열에 대해 하나와 반전 된 문자열에 대해 하나씩 두 개의 배열을 사용할 것입니다. 그런 다음 String의 해시 값을 저장합니다. 여기서 해시 값은 서로 다를 수 있습니다. String []에 대해 해시 값을 취하고 반전 된 문자열에 대해 해시 값을 반대로한다고 가정합니다. 접두사와 접미사 배열을 사용할 것입니다.

String str :“aabbbababaaa”가 있다고 가정합니다.

str의 해시 값을 다음과 같이 저장합니다.

접두사 [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) = "bbb"의 해시 값을 찾으려면 다음과 같이됩니다.

접두사 [5] – 접두사 [2] = 98 * 1013 + 98 * 1014 + 98 * 1015.

이 값은 회문을 찾는 데 도움이됩니다. 접미사 배열로도 똑같이 할 것이기 때문에 이번에는 마지막으로 방법을 살펴 보겠습니다.

문자열 str : "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.

이제 다음을 사용하여 역 해시 값의 값을 계산할 수 있습니다.

역 해시 값 (왼쪽, 오른쪽) : 해시 값 (오른쪽, 왼쪽) = 접미사 [n- 왼쪽] – 접미사 [n- 오른쪽 -1].

예 : 문자열 str : "aabbbababaaa".

역 해시 값 : substring (2,4) :

"bbba"의 값을 반대로하면 "abbb"가됩니다.

Suffix [11-1] – suffix [11-4-1] = suffix [10] -suffix [6].

그리고 지금 우리는 회문이 존재하는지 알아내는 방정식을 가지고 있습니다.

이제 우리는 접두사와 접미사로 두 개의 배열을 가지고 있으며, 그들 사이에 관계가 있습니다.

(접두사 [오른쪽 + 1] – 접두사 [왼쪽])  =  (접미사 [n – 왼쪽] – 접미사 [n – 오른쪽-1])

(101좌회전) (101n – 오른쪽 – 1)

 

회문 하위 문자열 쿼리

암호

회문 하위 문자열 쿼리에 대한 C ++ 코드

#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 하위 문자열 쿼리를위한 Java 코드

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

복잡성 분석

시간 복잡성

O (N + Q) 어디에 "엔" 문자열의 크기이고 "큐" 수행 할 쿼리 수입니다. 따라서 알고리즘은 O (1) 시간에 각 쿼리에 응답하므로 선형 시간 복잡도를 갖습니다.

공간 복잡성

의 위에) 어디에 "엔" 주어진 문자열의 문자 수입니다. 문자열에 대한 해시 값을 저장했기 때문입니다. 추가 공간을 사용했습니다.

Translate »