回文串判断算法,最长回文子串算法

目录1，判断字符串为回文列2，寻找字符串中有几个回文部分列1，暴力列举2、中心扩张法3、动态计划4、Manacher (慈爱乌冬面车)算法3、回文部分列的最大长度

一.判断字符串为回文字符串

回文串：字符串翻转后与原始字符串相同。 例如aba

判断代码如下，考虑从头尾开始依次比较，如果全部相同，则意味着是回文串

时间复杂度为o(n )，空间复杂度为o ) )1)

//字符串i-j为回文字符串boolispalindromic(strings，int i，int j ) (while ) Ij ) ) if ) s[I]！=s[j--]{returnfalse； } }返回真； )二、查找字符串中有多少个回文子串(1、暴力枚举直接遍历整个字符串

时间复杂度为o(n3 )，空间复杂度为o )1)

intcountsubstrings(strings ) {int count=0； int len=s.size (； for(intI=0； i len； I ) for(intj=I； j len； j () if ) ispalindromic(s，I，j )==true ) {count； } } }返回计数； ) 2、因为中心扩张法的回文列是对称的，所以如果在回文列的头尾添加相同的字符，则得到的新字符串一定是回文列。

这样扫描时，从一个中心点向两侧扩展，判断左右边是否相等即可。 这样就不需要每次都从头开始遍历

时间复杂度为o(n2 )，空间复杂度为o )1)

intcountsubstrings(strings ) {int len=s.size，count=0； if(len==0) { return 0； }for(intI=0； i len； I ) ) /回文串有奇数和偶数的长度，中心点的长度为1和2个count=expandaroundcenter(s，I，I )； 从//1字符扩展count=expandaroundcenter(s，I，i 1 )；//从两个字符之间扩展(} return count； }intexpandaroundcenter(strings，int left，int right ) int left，r=right，count=0； int len=s.size (； while(L=0rlens[L]==s[R] ) L--； r； 出局； }返回计数； }代码优化，看看上面的代码。 在最后一次扫描中，i 1超出了数组的范围，所以该次没有被扫描

因此，得知扫描中心点的数量为2 * len - 1，分别为len个1个文字和len - 1个2个文字。

举一个例子，有ABA:a、ab、b、ba、a这5个中心点

intcountsubstrings(strings ) {int n=s.size )，count=0； //因为要进行遍历，所以需要将中心点for(intI=0； i 2 * n - 1； I ) (/单个中心点l和r重合的int l=i/2，r=i/2 i % 2； wile(L=0rns[L]==s[R] ) { --l； r； 出局； } }返回计数； } 3、在确认动态计划开头字符相等的情况下，如果中间字符串是回文串，则可以确认当前字符串是回文串。

这样，可以用二维数组记录字符串是否为回文列，并可以像填写表那样传递各个字符

字符串是否为回文字符串。

时间复杂度为o(n2 )，空间复杂度为o ) n2 )

intcountsubstrings(strings ) {int count=0； int len=s.length； bool **dp=new bool*[len]； for(intI=0； i len； I ) {dp[i]=new bool[len]； for(intj=0； j len； j({DP[I][j]=false； }for(intj=0； j len； j ) for(intI=0； i=j； I ) {

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 <int> (n); //最大回文串的中心点坐标 int id_max = 0; //最大回文串右端点 int r_max = 0; //回文子串数量 int count = 0; for (int i = 1; i < n;i++) { /* 初始化 f[i]，最关键的代码 i <= r_max 代表当前点在最大回文串里面，在这个回文串里面i有个对称点j = 2*id_max-1，r_max的对称点l_max， 根据回文串的对称性，[i,r_max]区间与[l_max,j]区间一定是相等的。 在以j为中心的回文里面有[j+f[j],j]、[j,j-f[j]]这两个对称区间一定是相等的， 在以j为中心的回文里面对称，[l_max,j]和[j,j-f[j]]的交集在[j+f[j],j]里面，然后在最大回文里面对称过去就是 i左边有和这个交集相同的字符串，这样i就是由左右两边这样的交集组成的回文，半径就是交集的大小， min(r_max - i + 1, f[j])就是计算交集的大小。 */ f[i] = (i <= r_max ) ? min(r_max - i + 1, f[2 * id_max - i]) : 1; //中心拓展，加减到边界时因为边界字符与其他字符都不同，一定会退出循环，而不会越界 while (s_new[i + f[i]] == s_new[i - f[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 ;} 三、回文子串最大长度

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