数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用 C++ 统计给定字符串中不重叠回文子字符串的对数
给定一个字符串作为输入，任务是找出给定输入字符串中不重叠回文子字符串的对数。如果子字符串是回文，则 arr[i][j] 的值为真，否则为假。我们将从字符串中取出组合，并检查这些对是否满足条件。
让我们通过示例来理解。
输入：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) 进行进一步处理。
- 最初创建了一个大小为 100 的布尔型二维数组 arr[ ][ ]，并保持自底向上填充，并将输入字符串 (text) 转换为字符数组。
- 然后通过检查值 arr[i+1][j-1] 来计算数组，如果该值为真且 str[i] 与 str[j] 相同，则我们将 arr[i][j] 设置为真。否则，arr[i][j] 的值设置为假。
- 之后初始化 start[ ] 和 end[ ]，start[i] 存储索引左侧回文数（包括 i），end[i] 存储索引右侧回文数（包括 i）。
- 然后迭代一个从 0 到 str.length() - 1 的循环，并在循环内部通过将结果与 start[i] * end[i + 1] 的乘积相加来计算结果。
示例
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
更新于： 2021-01-29
331 次查看
广告