# 回文子串查询

## 使用案列

```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```

## 途径

```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.```

prefix [5] – prefix [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.```

（前缀[Right +1] –前缀[Left]）  =  （后缀[n –左] –后缀[n –右1]）

（101离开）（101n –对– 1)

## 代码

### Palindrome子字符串查询的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```

### 回文子字符串查询的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） 哪里 “N” 是字符串的大小，并且 “ Q” 是要执行的查询数。 因此，该算法具有线性时间复杂度，因为我们在O（1）时间内回答了每个查询。