计算C ++中给定字符串的不重叠回文子字符串对
给我们一个字符串形式的输入，任务是找出给定输入字符串的不重叠回文子字符串对的计数。如果子字符串是回文，则arr[i][j]的值为true，否则为false。我们将从字符串中取出组合，并检查对是否满足条件。
让我们通过示例来理解。
输入：ABC
输出： 非重叠回文子字符串的对数为3
说明： 可能的对是(A)(B)(C)，(A)(BC)，(AB)(C)，(ABC)
输入：ABCD
输出： 非重叠回文子字符串的对数为8
说明：可能的对是(A)(B)(C)(D)，(A)(B)(CD)，(A)(BC)(D)，(A)(BCD)，(AB)（C）(D)，(AB)(CD)，
(ABC)(D)，(ABCD)
以下程序中使用的方法如下
将字符串作为输入并传递到函数中pair_count(text)以进行进一步处理。
最初，创建并维护一个大小为100arr[][]的布尔2D数组，并以自下而上的方式进行填充，然后将输入string(text)转换为字符数组。
然后通过检查值arr[i+1][j-1]来计算数组，如果该值为true且str[i]与str[j]相同，则使arr[i][j]真的。否则，将arr[i][j]的值设为false。
之后，对start[]和end[]进行初始化，并且start[i]在的左侧index(includingi)存储回文数的回文数，而end[i]在该函数的右侧存储元素数的回文数。index(includingi)
然后从0到-1循环，并在循环内通过将结果与start[i]*end[i+1]的乘积相加来计算结果。str.length()
示例
import java.io.*;
import java.util.*;
class tutorialPoint {
static int SIZE = 100;
static int pair_count(String str) {
boolean arr[][] = new boolean[SIZE][SIZE];
char[] ch = str.toCharArray();
for (int i = 0; i < ch.length; i++) {
for (int j = 0; j < ch.length; j++) {
arr[i][j] = false;
}
}
for (int j = 1; j <= ch.length; j++) {
for (int i = 0; i <=ch.length- j; i++) {
if (j <= 2) {
if (ch[i] == ch[i + j - 1]) {
arr[i][i + j - 1] = true;
}
} else if (ch[i] == ch[i + j - 1]) {
arr[i][i + j - 1] = arr[i + 1][i + j - 2];
}
}
}
int start[] = new int[str.length()];
int end[] = new int[str.length()];
start[0] = 1;
for (int i = 1; i < str.length(); i++) {
for (int j = 0; j <= i; j++) {
if (arr[j][i] == true) {
start[i]++;
}
}
}
end[str.length() - 1] = 1;
for (int i = str.length() - 2; i >= 0; i--) {
end[i] = end[i + 1];
for (int j = str.length() - 1; j >= i; j--) {
if (arr[i][j] == true) {
end[i]++;
}
}
}
int result = 0;
for (int i = 0; i < str.length() - 1; i++) {
result = result + start[i] * end[i + 1];
}
return result;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in); //ABCD
String text = scan.next();
System.out.println("Count pairs of non-overlapping palindromic sub-strings is\t" + pair_count(text));
}
}如果我们运行上面的代码，它将生成以下输出-
输出结果
Count pairs of non-overlapping palindromic sub-strings is 8