计算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