关于回文串的几种常见算法总结

您所在的位置：网站首页 › 两个字符串相加是否是新的实例呢 › 关于回文串的几种常见算法总结

关于回文串的几种常见算法总结

2023-09-13 13:57| 来源: 网络整理| 查看: 265

目录一、判断字符串为回文串二、查找字符串中有多少个回文子串1、暴力枚举2、中心扩展法3、动态规划4、Manacher（马拉车）算法三、回文子串最大长度

一、判断字符串为回文串

回文串：字符串反转后和原字符串相同同，比如aba 判断代码如下，思路是从头尾开始依次比较，全部相同就代表是回文串时间复杂度为O(n)，空间复杂度O(1)

//判断字符串i-j是否为回文串 bool isPalindromic(string &s,int i,int j) { while(i return false; } } return true; } 二、查找字符串中有多少个回文子串 1、暴力枚举

直接遍历整个字符串时间复杂度为O(n3)，空间复杂度O(1)

int countSubstrings(string s) { int count = 0; int len = s.size(); for(int i = 0;i if(isPalindromic(s,i,j) == true) { count++; } } } return count; } 2、中心扩展法

回文串是对称的，所以在回文串头尾添加一个相同的字母，得到的新的字符串一定是回文串。这样我们在遍历时从一个中心点开始向两边扩展，判断左右两边是否相等即可。这样就不用每次都从头开始遍历时间复杂度为O(n2)，空间复杂度O(1)

int countSubstrings(string s) { int len = s.size(),count = 0; if (len == 0) { return 0; } for (int i = 0; i int l = left, r = right,count = 0; int len = s.size(); while (l >= 0 && r int n = s.size(), count = 0; //遍历所以中心点 for (int i = 0; i --l; ++r; ++count; } } return count; } 3、动态规划

当确认首位字符相等时，我们只需要中间字符串是回文串，就可以确认当前字符串是回文串。这样我们可以用一个二维数组去记录字串是否为回文串，就可以向填表一样递推出每个字符串是否为回文串。时间复杂度为O(n2)，空间复杂度O(n2)

int countSubstrings(string s) { int count = 0; int len = s.length; bool **dp = new bool*[len]; for (int i = 0;i dp[i][j] = false; } } for (int j = 0;j if (i == j) // 单个字符 { dp[i][j] = true; count++; } else if (j - i == 1 && s[i] == s[j]) // 两个字符 { dp[i][j] = true; count++; } else if (j - i > 1 && s[i] == s[j] && dp[i + 1][j - 1]) // 多于两个字符 { dp[i][j] = true; count++; } } } return count; }; 4、Manacher（马拉车）算法

马拉车算法很巧妙，利用了回文串对称的特性尽最大的努力去减少中心扩展的比较次数，不会无脑的去比较而是把前面的状态记录下来加以利用。因为马拉车算法的最大回文右端点r_max只会变大不会变小，所以遍历的次数不会超过过n 时间复杂度为O(n)，空间复杂度O(n)

int countSubstrings(string s) { int n = s.size(); //字符串前后加@$是当作边界，就不用去判断边界了，边界符号与插入符号、字符串包含的符号都不能相同 string s_new = "@#"; for (const char &c: s) { s_new += c; //插入符号，添加插入符号的作用是不用去管原字符串是奇数还是偶数，统一变成奇数的字符串 s_new += '#'; } n = s_new.size(); s_new += '$'; //记录状态数组，数组内容是以当前点为中心能够扩展回文串最大的半径 auto f = vector (n); //最大回文串的中心点坐标 int id_max = 0; //最大回文串右端点 int r_max = 0; //回文子串数量 int count = 0; for (int i = 1; i f[i]++; } //更新 id_max 和 r_max if (i + f[i] - 1 > r_max ) { id_max = i; r_max = i + f[i] - 1; } //去掉插入符号组成的回文串 count += (f[i] / 2); } return count ; } 三、回文子串最大长度

上面几种算法都遍历的所有子串，只需要在每次确认字串时记录当前子串长度，找出最大的子串即可。

【本文地址】

关于回文串的几种常见算法总结

关于回文串的几种常见算法总结

今日新闻

推荐新闻