计算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)以进行进一步处理。

  • 最初,创建并维护一个大小为100 arr [] []的布尔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(including i)存储回文数的回文数,而end [i]在该函数的右侧存储元素数的回文数。index(including i)

  • 然后从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

以上是 计算C ++中给定字符串的不重叠回文子字符串对 的全部内容, 来源链接: utcz.com/z/320057.html

回到顶部