C ++中索引范围内的回文子串计数

  • Z时代
  • 2024-01-10
  • 分类：综合

给我们一个字符串，从开始到结束的范围，任务是计算给定范围内回文子字符串的计数。回文字符串是从字符串的前向和后向相似的字符串，例如nitin，aba等。

例如

输入 -InputString =“ cccaabbbdee”，开始= 2，结束= 6;

输出- 索引范围7中的回文子串计数

说明- 我们给定了一个范围和一个字符串，因此，我们将从开始指针2（即'c'）开始遍历该字符串，直到6即'b'遍历该字符串，因此子字符串为'caabb'。因此回文子串是'c'，'a'，'a'，'b'，'b'，'aa'和'bb'。因此，回文子串的计数为7。

输入 -InputString =“ lioaabbbdee”，开始= 0，结束= 2；

输出- 索引范围3中的回文子串计数

说明- 我们给出了一个范围和一个字符串，因此，我们将从起始指针0（即“ l”）开始遍历字符串，直到2即“ o”，因此子字符串为“ lio”。因此回文子串是“ l”，“ i”和“ o”。因此，回文子串的计数为3。

以下程序中使用的方法如下

  • 声明任何给定大小的字符串，其范围从变量开始到结束。

  • 将数据传递给命名的函数以palindrome_index(arr, InputString)进行进一步处理

  • 在函数内部，声明另一个名为checked的数组，其大小为array。

  • 从0开始到i的循环直到数组的长度

  • 在循环内部，从0到数组的长度开始另一个Loop FOR j

  • 在循环内部，将check设置为check [i] [j] = 0和arr [i] [j] = 0

  • 从长度-1到i大于0开始对i进行循环 

  • 在循环内部，将i的check和arr设置为1，然后从i +1开始另一个循环FOR j，直到数组的长度

  • 在循环内，检查ii处的IF字符串等于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] +选中[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("索引范围内回文子串的计数 " + arr[start][end]);
   }
}

如果我们运行上面的代码，它将生成以下输出-

输出结果

索引范围内回文子串的计数 7

以上是 C ++中索引范围内的回文子串计数 的全部内容， 来源链接： utcz.com/z/325140.html

回到顶部