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

给我们一个字符串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

回到顶部