浙江福彩3d走势图
我們來自五湖四海,不為別的,只因有共同的愛好,為中國互聯網發展出一分力!

最長回文串算法

2013年10月08日21:04 閱讀: 15707 次
給定一個字符串找出最長回文字符串范圍,例如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 <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
  
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.
分享到: 更多
藍客門戶
©2001-2019 中國藍客聯盟 版權所有.
關于藍客聯盟歷史宗旨章程技術服務聯系我們藍客社區

浙江福彩3d走势图 广东36选7走势图走图 足球手抄报版面设计图大全 彩友网网址 魔域卖宝宝赚钱 湖南快乐10分中奖规则 北京时时彩赛车开奖记录 湖南快乐十分遗漏 快乐8稳赚技巧 在温州卖山寨手机赚钱嘛 星力捕鱼游戏