我们来自五湖四海,不为别的,只因有共同的爱好,为中国互联网发展出一分力!

最长回文串算法

2013年10月08日21:04 阅读: 16092 次
给定一个字符串找出最长回文字符串范围,例如abaabac,最长回文为abaaba
1、使用暴力的算法需要O(N^3)的复杂度,需要O(N^2)的复杂度去运算字符串所用的子串,然后使用O(N)去判断是否是回文串,从而定位最长的回文子串。
[cpp] ?
int lps_bl(char str[], int len){ ?
? ? if(str == NULL || len <= 0){ ?
? ? ? ? return 0; ?
? ? } ?
? ? int i, j; ?
? ? int start, end, max_lps; ?
? ? for(i = 0; i < len; i++){ ?
? ? ? ? for(j = 1; j < len; j++){ ?
? ? ? ? ? ? start = ?0; ?
? ? ? ? ? ? end = len - 1; ?
? ? ? ? ? ? while(start <= end && str[start] == str[end]){ ?
? ? ? ? ? ? ? ? start++; ?
? ? ? ? ? ? ? ? end--; ?
? ? ? ? ? ? } ?
? ? ? ? ? ? if(start >= end){ ?
? ? ? ? ? ? ? ? if(j > max_lps){ ?
? ? ? ? ? ? ? ? ? ? max_lps = j; ?
? ? ? ? ? ? ? ? } ?
? ? ? ? ? ? } ?
? ? ? ? } ?
? ? } ?
? ? printf("lps_bl:%d\n", max_lps); ?
? ? return max_lps; ?
} ?
?
可以看到这种算法很容易理解,只是O(N^3)的复杂度相对比较高。
2、使用动态规划的思想进行求解,思路是利用子串从短到长进行逐步的动态规划求解,可以理解为从中心向两边扩散,如果一个字符串的子串是回文串,那么就可以存储这个状态,然后从短向长蔓延进行计算:
当i == j 时 肯定是长度为1 的回文串,dp[i][j] = 1
当dp[i][j] == 1 时如果S[i-1] == S[j+1], dp[i][j] == 1,(如果子串是回文串,并且首尾相同,那么当前的子串也是回文串)
当i+1 == j 时,S[i] == S[j], 那么dp[i][j] == 1,这个状态值在计算时会有些特殊,因为 j = i +1,那么i-1和j+1会与i和j的值相反,但是不影响整体的计算。
[cpp]?
#include ?
#include ?
#include ?
??
int lps_dp(char str[], int len) ?
{ ?
? ? if(str == NULL || len <= 0){ ?
? ? ? ? return 0; ?
? ? } ?
? ? int dp[100][100] = {0}; ?
? ? int i,j, m; ?
? ? for(i = 0; i < 100; i++){ ?
? ? ? ? dp[i][i] = 1; ?
? ? } ?
? ? int start = 0; ?
? ? int end = 0; ?
? ? int max_lps = 0; ?
? ? char buf[100] = {0}; ?
? ? //printf("len:%d\n", len); ?
? ? for(m = 1; m < len; m++){ ?
? ? ? ? printf("m=%d\n", m); ?
? ? ? ? for(i = 0; i < len - m; i++){ ?
? ? ? ? ? ? j = i + m; ?
? ? ? ? ? ? memcpy(buf, str + i, j-i + 1); ?
? ? ? ? ? ? buf[j-i + 1] = '\0'; ?
? ? ? ? ? ? //printf("%d\t%d\t%s\n", i, j,buf); ?
? ? ? ? ? ? //printf("dp[%d][%d]=%d\n", (i+1), (j-1), dp[i+1][j-1]); ?
? ? ? ? ? ? if(i + 1 == j && str[i] == str[j]){ ?
? ? ? ? ? ? ? ? dp[i][j] = 1; ?
? ? ? ? ? ? ? ? int tmp = j - i + 1; ?
? ? ? ? ? ? ? ? if(tmp > max_lps){ ?
? ? ? ? ? ? ? ? ? ? start = i; ?
? ? ? ? ? ? ? ? ? ? end = j; ?
? ? ? ? ? ? ? ? ? ? max_lps = tmp; ?
? ? ? ? ? ? ? ? } ?
? ? ? ? ? ? }else if(dp[i+1][j-1] == 1 && str[i] == str[j]){ ?
? ? ? ? ? ? ? ? dp[i][j] = 1; ?
? ? ? ? ? ? ? ? int tmp = j - i + 1; ?
? ? ? ? ? ? ? ? if(tmp > max_lps){ ?
? ? ? ? ? ? ? ? ? ? start = i; ?
? ? ? ? ? ? ? ? ? ? end = j; ?
? ? ? ? ? ? ? ? ? ? max_lps = tmp; ?
? ? ? ? ? ? ? ? } ?
? ? ? ? ? ? } ?
? ? ? ? } ?
? ? } ?
? ? //memcpy(buf, str+start, max_lps); ?
? ? //buf[max_lps] = '\0'; ?
? ? //printf("max_len:%d\tlps:%s\n", max_lps, buf); ?
? ? return max_lps; ?
} ?
?
3、受以上动态规划算法的启发,可以考虑选取中间点,然后逐步向两边蔓延的策略进行回文串的判断,这种方法相对于动态规划的算法更容易理解,而且空间复杂度会由O(N^2)变为O(1)
[cpp] ?
int lps_ext(char str[], int len){ ?
? ? if(str == NULL || len <= 0){ ?
? ? ? ? return 0; ?
? ? } ?
? ? int i; ?
? ? int max_lps = 1; ?
? ? int start = 0; ?
? ? char buf[100] = {0}; ?
? ? for(i = 1; i < len; i++){ ?
? ? ? ? int low = i - 1; ?
? ? ? ? int high = i; ?
? ? ? ? while(low >= 0 && high < len && str[low] == str[high]){ ?
? ? ? ? ? ? if(high - low + 1> max_lps){ ?
? ? ? ? ? ? ? ? start = low; ?
? ? ? ? ? ? ? ? max_lps = high - low + 1; ?
? ? ? ? ? ? } ?
? ? ? ? ? ? low--; ?
? ? ? ? ? ? high++; ?
? ? ? ? } ?
? ? ? ? low = i - 1; ?
? ? ? ? high = i + 1; ?
? ? ? ? while(low >= 0 && high < len && str[low] == str[high]){ ?
? ? ? ? ? ? if(high - low + 1 > max_lps){ ?
? ? ? ? ? ? ? ? start = low; ?
? ? ? ? ? ? ? ? max_lps = high - low +1; ?
? ? ? ? ? ? } ?
? ? ? ? ? ? low--; ?
? ? ? ? ? ? high++; ?
? ? ? ? } ?
? ? } ?
? ? memcpy(buf, str + start, max_lps); ?
? ? printf("%d\tlps_ext:%s\n",max_lps, buf); ?
? ? return max_lps; ?
??
} ?
?
下面介绍一种O(N)的算法:Manacher, 这个算法开始理解起来比较复杂,但确实有一定的技巧性,第一个技巧是将可能的回文串,无论是奇数个字符还是偶数个字符全部变为奇数,这样有利于利用对称性特征进行计算,变换方式如下:
在每个字符的两边都插入一个特殊的符号。比如 abba 变成 #a#b#b#a#, aba变成 #a#b#a#。 为了进一步减少编码的复杂度,可以在字符串的开始加入另一个特殊字符,这样就不用特殊处理越界问题,比如$#a#b#a#。
下面以字符串12212321为例,经过上一步,变成了 S[] = "$#1#2#2#1#2#3#2#1#";
算法引入两个变量id和mx,id表示最长回文子串的中心位置,mx表示最长回文字串的边界位置,即:mx=id+P[id]。
在这里有一个非常有用而且神奇的结论:如果mx > i,那么P[i] >= MIN(P[2 * id - i], mx - i) 分开理解就是:
如果mx - i > P[j], 则P[i]=P[j]
否则,P[i] ?= mx - i.
分享到: 更多
蓝客门户