本文共 5360 字,大约阅读时间需要 17 分钟。
子串的含义是:在原串中连续出现的字符串片段。回文的含义是:正着看和倒着看相同,如abba和yyxyy。
给出一个长度不超过1000的字符串,判断它是不是回文(顺读,逆读均相同)的。
https://www.nowcoder.com/practice/df00c27320b24278b9c25f6bb1e2f3b8?tpId=69&&tqId=29674&rp=1&ru=/activity/oj&qru=/ta/hust-kaoyan/question-ranking
思路:从两端开始对比,如果相等,则开始缩小范围,继续对比;如果不等则返回false
public static boolean Palindrome(char []array){ if(array.length==0||array.length==1) return true; int i=0; int j=array.length-1; while(i=j) return true; else return false; }
输入一个字符串,求出其中最大的回文子串。
1. Brute-force 解法对于最长回文子串问题,最简单粗暴的办法是:找到字符串的所有子串,遍历每一个子串以验证它们是否为回文串。一个子串由子串的起点和终点确定,因此对于一个长度为n的字符串,共有n^2个子串。这些子串的平均长度大约是n/2,因此这个解法的时间复杂度是O(n^3)。
2. 改进的方法
显然所有的回文串都是对称的。长度为奇数回文串以最中间字符的位置为对称轴左右对称,而长度为偶数的回文串的对称轴在中间两个字符之间的空隙。可否利用这种对称性来提高算法效率呢?答案是肯定的。我们知道整个字符串中的所有字符,以及字符间的空隙,都可能是某个回文子串的对称轴位置。可以遍历这些位置,在每个位置上同时向左和向右扩展,直到左右两边的字符不同,或者达到边界。对于一个长度为n的字符串,这样的位置一共有n+n-1=2n-1个,在每个位置上平均大约要进行n/4次字符比较,于是此算法的时间复杂度是O(n^2)。
3. Manacher 算法(中文名:马拉车算法)
由于回文分为偶回文(比如 bccb)和奇回文(比如 bcacb),而在处理奇偶问题上会比较繁琐,所以这里我们使用一个技巧,具体做法是,在字符串首尾,及字符间各插入一个字符(前提这个字符未出现在串里)。 举个例子:s="abbahopxpo",转换为s_new="$#a#b#b#a#h#o#p#x#p#o#"(这里的字符 $ 只是为了防止越界,下面代码会有说明),如此,s 里起初有一个偶回文abba和一个奇回文opxpo,被转换为#a#b#b#a#和#o#p#x#p#o#,长度都转换成了奇数。
定义一个辅助数组int p[],其中p[i]表示以 i 为中心的最长回文的半径,例如:
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
s_new[i] | $ | # | a | # | b | # | b | # | a | # | h | # | o | # | p | # | x | # | p | # |
p[i] | 1 | 2 | 1 | 2 | 5 | 2 | 1 | 2 | 1 | 2 | 1 | 2 | 1 | 2 | 1 | 4 | 1 | 2 | 1 |
下面计算p[i],该算法增加两个辅助变量id和mx,其中id表示最大回文子串中心的位置,mx则为id+p[id],也就是最大回文子串的边界。
这个算法的关键点就在这里了:如果mx > i,那么p[i] >= MIN(p[2 * id - i], mx - i);对于 mx <= i 的情况,无法对 p[i]做更多的假设,只能p[i] = 1,然后再去匹配了。2 * id - i
为 i 关于 id 的对称点(j=id+(id-i)=2*id-i),即上图的 j 点,而p[j]
表示以 j 为中心的最长回文半径,因此我们可以利用p[j]
来加快查找。
其实就是p[i] >= MIN(p[j], mx - i),就是求二者的最小值,当情况一时,p[j]=p[i]<mx-i;当情况二时,p[j]>mx-i;
if(mx > i){ p[i] = (p[2*id - i] < (mx - i) ? p[2*id - i] : (mx - i));}else{ p[i] = 1;}根据回文的性质,
p[i]
的值基于以下三种情况得出: 当 mx - i > P[j] 的时候,以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中,由于 i 和 j 对称,以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中,所以必有 P[i] = P[j],见下图。
p[i] = p[j]
,那么p[i]
还可以更大么?答案亦是不可能!见下图: p[i]
可以增加的部分,那么根据回文的性质,a 等于 b ,也就是说 j 的回文应该再加上 a 和 b ,矛盾,所以假设不成立,故p[i] = p[j]
,也不可以再增加一分。
当 P[j] > mx - i 的时候,以S[j]为中心的回文子串不完全包含于以S[id]为中心的回文子串中,但是基于对称性可知,下图中两个绿框所包围的部分是相同的,也就是说以S[i]为中心的回文子串,其向右至少会扩张到mx的位置,也就是说 P[i] >= mx - i。至于mx之后的部分是否对称,就只能一个一个匹配了。
p[i] = mx - i
,即紫线。那么p[i]
还可以更大么?答案是不可能!见下图: p[i]
可以增加的部分,那么根据回文的性质,a 等于 d ,也就是说 id 的回文不仅仅是黑线,而是黑线 + 两条紫线,矛盾,所以假设不成立,故p[i] = mx - i
,不可以再增加一分。 (3)j 回文串左端正好与 id 的回文串左端重合,例如:mabcdbcaxacbdcbax
p[i] = p[j]
或p[i] = mx - i
,并且p[i]
还可以继续增加,所以需要 while (s_new[i - p[i]] == s_new[i + p[i]]) p[i]++;
public static char[] initChr(char[] ch) {//初始化字符串 // TODO Auto-generated method stub char s_new[]=new char[2*ch.length+1];// s_new[0]='$'; s_new[0]='#'; int j=1; for(int i=0;i
public static int getLongestPalindrome(String A) {//求最长回文子串的长度 char[] ch=A.toCharArray(); char s_new[]=initChr(ch); int len=s_new.length; int id=0; int mx=0; int max_len=0; int p[]=new int[len]; for(int i=0;i=0 && i+p[i] mx) { id=i; mx=i+p[i]; } max_len= Math.max(max_len,p[i]); } return max_len-1; }
以上for循环中为此算法的核心,掌握住可以在此扩展。
public static String getLongestPalindrome2(String A) {//求最长回文子串 char[] ch=A.toCharArray(); char s_new[]=initChr(ch); int len=s_new.length; int id=0; int mx=0; int max_len=0; int max_index=0; int p[]=new int[len]; for(int i=0;i=0 && i+p[i] mx) { id=i; mx=i+p[i]; } if(max_len
public static String addToPalindrome(String A) {//结尾添加最短字符串,使其变为回文串 char []ch = A.toCharArray(); char s_new []=initChr(ch); int id=0; int mx=0; int p[]=new int[s_new.length]; int i=0; for(i=0;i=0 && s_new[i-p[i]]==s_new[i+p[i]]) { p[i]++; } if(i+p[i]>mx) { id=i; mx=i+p[i]; } //最右回文半径到达字符串最右边界的位置时,跳出循环,找到此时的中心id和此中心的回文半径(p[i]-1) if(mx==s_new.length) { break; } } char final_ch []=new char[(id-(p[i]-1))/2]; for(int j=id-p[i],k=0;j>=0;j--) { if(s_new[j]!='#') { final_ch[k++]=s_new[j]; } } return new String(final_ch); }
public int longestPalindrome(String s) { int n=s.length(); boolean[][] pal=new boolean[n][n]; //pal[i][j] 表示s[i...j]是否是回文串 int maxLen=0; for (int i=0;i=0){ if (s.charAt(j)==s.charAt(i)&&(i-j<2||pal[j+1][i-1])){ pal[j][i]=true; maxLen=Math.max(maxLen, i-j+1); } j--; } } return maxLen; }