数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中指定索引范围内的回文子串计数
给定一个字符串和一个从start到end的范围，任务是计算给定范围内回文子串的数量。回文串是指从前向后和从后向前都相同的字符串，例如nitin、aba等。
例如
输入 - InputString = "cccaabbbdee", start = 2, end = 6;
输出 - 索引范围内的回文子串计数：7
说明 - 给定一个范围和一个字符串，我们将从起始指针2（即'c'）遍历到6（即'b'），因此子串是'caabb'。所以回文子串是'c'、'a'、'a'、'b'、'b'、'aa'和'bb'。因此，回文子串的计数是7。
输入 - InputString = "lioaabbbdee", start = 0, end = 2;
输出 - 索引范围内的回文子串计数：3
说明 - 给定一个范围和一个字符串，我们将从起始指针0（即'l'）遍历到2（即'o'），因此子串是'lio'。所以回文子串是'l'、'i'和'o'。因此，回文子串的计数是3。
下面程序中使用的方法如下
- 声明一个任意大小的字符串和一个从变量start到end的范围。
- 将数据传递给名为palindrome_index(arr, InputString)的函数进行进一步处理
- 在函数内，声明另一个名为checked的数组，数组大小与输入数组相同。
- 开始循环FOR i 从0到数组长度
- 在循环内，开始另一个循环FOR j 从0到数组长度
- 在循环内，设置check为check[i][j] = 0，arr[i][j] = 0
- 开始循环FOR i 从长度-1到i大于0
- 在循环内，将check和arr的i设置为1，然后开始另一个循环FOR j 从i+1到数组长度
- 在循环内，检查IF字符串i等于字符串j，并且i+1大于j-1或check[i+1][j-1]不等于0，则将check[i][j]设置为1，否则，将check[i][j]设置为0，然后设置arr[i][j] = arr[i][j-1] + arr[i+1][j] - arr[i+1][j-1] + check[i][j]
- 打印一个二维数组作为起始和结束。
示例
import java.io.*;
class testqwe {
static void palindrome_index(int arr[][], String s) {
int length = s.length();
int[][] check = new int[length + 1][length + 1];
for (int i = 0; i <= length; i++) {
for (int j = 0; j <= length; j++) {
check[i][j] = 0;
arr[i][j] = 0;
}
}
for (int i = length - 1; i >= 0; i--) {
check[i][i] = arr[i][i] = 1;
for (int j = i + 1; j < length; j++) {
if(s.charAt(i) == s.charAt(j) && (i + 1 > j - 1 || (check[i + 1][j - 1]) != 0)) {
check[i][j] =1;
} else {
check[i][j] =0;
}
arr[i][j] = arr[i][j - 1] + arr[i + 1][j] - arr[i + 1][j - 1] + check[i][j];
}
}
}
public static void main(String args[]) {
String InputString = "cccaabbbdee";
int[][] arr;
arr = new int[50][50];
palindrome_index(arr, InputString);
int start = 2;
int end = 6;
System.out.println("Count of Palindromic substrings in an Index range " + arr[start][end]);
}
}如果我们运行上面的代码，它将生成以下输出：
输出
Count of Palindromic substrings in an Index range 7
更新于：2021年1月29日
211 次浏览
广告