在C ++中计算字符串中的特殊回文

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

给我们一个字符串str。目的是计算所有属于特殊回文且长度大于1的str子字符串。特殊回文是具有相同字符或仅具有不同中间字符的字符串。例如，如果字符串是“ baabaa”，则原始子字符串的特殊回文是“ aa”，“ aabaa”，“ aba”，“ aa”

让我们通过示例来理解。

输入-str =“ abccdcdf”

输出-字符串中的特殊回文数为-3

说明-特殊回文的子字符串为-“ cc”，“ cdc”，“ dcd”

输入-str =“ baabaab”

输出-字符串中的特殊回文数为-4

说明-特殊回文的子字符串为-“ aa”，“ aabaa”，“ aba”，“ aa”

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

  • 创建一个字母字符串并计算其长度。将数据传递给函数进行进一步处理。

  • 声明一个临时变量count并将i设置为0

  • 创建一个字符串大小的数组，并将其初始化为0。

  • 从WHILE开始，直到我小于字符串的长度

  • 在while内，将变量total设置为1并将变量j设置为i + 1

  • 开始另一个WHILE，直到str [i] = str [j]和j小于字符串的长度

  • 在while内，将总数加1，将j加1

  • 将计数设置为count +（total *（total + 1）/ 2，arr [i]等于total，i等于j

  • 从j到1开始循环FOR，直到字符串的长度

  • 检查str [j] = str [j-1]，然后将arr [j]设置为arr [j-1]

  • 将变量temp设置为str [j-1]并检查j> 0 AND j <字符串长度是否小于AND AND temp = str [j + 1] AND sr [j]！= temp，然后将count设置为count + min（arr [j-1]，arr [j + 1]）

  • 设置计数-字符串的长度

  • 返回计数

  • 打印结果。

示例

#include <bits/stdc++.h>
using namespace std;
int count_palindromes(string str, int len){
   int count = 0, i = 0;
   int arr[len] = { 0 };
   while (i < len){
      int total = 1;
      int j = i + 1;
      while (str[i] == str[j] && j < len){
         total++;
         j++;
      }
      count += (total * (total + 1) / 2);
      arr[i] = total;
      i = j;
   }
   for (int j = 1; j < len; j++){
      if (str[j] == str[j - 1]){
         arr[j] = arr[j - 1];
      }
      int temp = str[j - 1];
      if (j > 0 && j < (len - 1) && (temp == str[j + 1] && str[j] != temp)){
         count += min(arr[j-1], arr[j+1]);
      }
   }
   count = count - len;
   return count;
}
int main(){
   string str = "bcbaba";
   int len = str.length();
   cout<<"Count of special palindromes in a String are: "<< count_palindromes(str, len);
   return 0;
}

输出结果

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

Count of special palindromes in a String are: 3

以上是 在C ++中计算字符串中的特殊回文 的全部内容， 来源链接： utcz.com/z/334689.html

回到顶部