-
By: admin
目录
一、判断字符串为回文串二、查找字符串中有多少个回文子串1、暴力枚举2、中心扩展法3、动态规划4、Manacher（马拉车）算法
三、回文子串最大长度
一、判断字符串为回文串
回文串：字符串反转后和原字符串相同同，比如aba 判断代码如下，思路是从头尾开始依次比较，全部相同就代表是回文串 时间复杂度为O(n)，空间复杂度O(1)
//判断字符串i-j是否为回文串
bool isPalindromic(string &s,int i,int j)
{
while(i < j)
{
if(s[i++] != s[j--])
{
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 < len;i++)
{
for(int j = i;j < len;j++)
{
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 < len; i++)
{
//回文串有奇数和偶数长度，中心点长度是1个和2个
count += expandAroundCenter(s, i, i); //从一个字符扩展
count += expandAroundCenter(s, i, i + 1); //从两个字符之间扩展
}
return count;
}
int expandAroundCenter(string &s, int left, int right)
{
int l = left, r = right,count = 0;
int len = s.size();
while (l >= 0 && r < len && s[l] == s[r])
{
l--;
r++;
count++;
}
return count;
}
代码优化，我们看上面代码，最后一次遍历，i+1是超出数组范围的，所以是没有遍历那一次的， 因此我们可以得出，遍历的中心点个数是 2 * len - 1；分别是 len 个单字符和 len - 1个双字符。 举个例子：aba：有 a、ab、b、ba、a五个中心点
int countSubstrings(string s)
{
int n = s.size(), count = 0;
//遍历所以中心点
for (int i = 0; i < 2 * n - 1; i++)
{
//单个中心点l 和 r重合
int l = i / 2, r = i / 2 + i % 2;
while (l >= 0 && r < n && s[l] == s[r])
{
--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 < len;i++)
{
dp[i] = new bool[len];
for(int j = 0;j < len;j++)
{
dp[i][j] = false;
}
}
for (int j = 0;j < len;j++)
{
for (int i = 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 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 ;
}
三、回文子串最大长度
上面几种算法都遍历的所有子串，只需要在每次确认字串时记录当前子串长度，找出最大的子串即可。