从Longest Palindromic Substring 学习了解Manacher’s Algorithm 马拉车算法

  • 1. 第一种解法是找到所有的子序列,然后依次判断这个子序列是不是回文字符串,这种解法的时间复杂度是0(N) * O (N) * O(N),运行结果912ms
  • 2. 利用动态规划减少计算的次数,时间复杂度是O(N) * O (N),空间复杂度是O(N) * O(N)
  • 3. 利用中心扩展法,如果是会问字符串的话,以该字符为中心两边的字符是相等的,如果相等,然后向外扩展
  • 4. Manacher’s Algorithm,很厉害的将时间复杂度降到了O(n),看了3天,看懂了,但是真正的自己写还是差了很多,同时通过这个算法,理解到了,真正的代码的思想其实 蕴含在数学中,所以我们平常一定要好好学习数学,还有在这个过程中,看的时候真的有点复杂,中文的并没有讲的特别清晰,只是给你讲了一个结论,看英文的真的很不容易,还有理解算法的时候中间很想放弃,但是不能放弃,如果你放弃了,下一次你遇见这个问题的时候你还是想要放弃,所以坚持下去,走过去,虽然很难,不要放弃呀,慢一点,没关系。如果你想要了解马拉车算法的话你可以看一下这几篇文章:

https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-1/

https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-2/

https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-3-2/

https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-4/

http://www.cnblogs.com/grandyang/p/4475985.html

//第一种解法:
bool isPalindromic(char *s,int start,int end)
{

    while (start <= end)
    {
        if (s[start] != s[end])
        {
            return false;
        }
        else
        {
            start++;
            end--;
        }
    }
    return true;
}



char* longestPalindrome(char* s)
{
    int i,j,k,len,maxLen,tmpLen;
    bool res;
    len = strlen(s);

    if (len <= 0)
    {
        return "";
    }
    char *ret = (char *)calloc(1001,sizeof(char));
    ret[0] = s[0];
    maxLen = 1;

    for (i = 0; i < len; i++)
    {
        for (j = i+1; j < len; j++)
        {

            res = isPalindromic(s,i,j);
            tmpLen = j - i;

            if (res && tmpLen >= maxLen)
            {
                maxLen = tmpLen;
                int count = 0;
                for (k = i; k <=j; k++)
                {
                    ret[count] = s[k];
                    count++;
                }
            }

        }
    }
    return ret;
}
//第二种解法 动态规划
char* longestPalindrome(char* s)
{
    // The time complexity can be reduced by storing results of subproblems.
    int len = strlen(s);

    if (len <= 0)
    {
        return "";
    }
    int i,j,k,start,maxLen;
    char *ret;
    int dp[len][len];

    // why memset set 1,print out not 1?
    // As memset works character by character and an integer cotains more than one bytes(or characters)
    // However,if we replace 10 with -1,we get -1 values.Because representation of -1 contains all 1s in case of both char and int.
    // Refer from https://www.geeksforgeeks.org/memset-c-example/

    memset(dp,0,sizeof(dp));

    /*
    for (i = 0;i < len;i++) {
        for (j = 0;j < len;j++) {
            printf("%d ",dp[i][j]);
        }
        printf("\n");
    }
    */

    // init maxLen,because one char is must Palindromic substring
    start = 0;
    maxLen = 1;

    //init dp when the char is one ,you need careful of here is dp[i][i],not dp[i][0]
    for (i = 0; i < len; i++)
    {
        dp[i][i] = 1;
    }

    // judge adjacent is equal,is equal is true,so maxLen is 2
    // here is len-1 not len
    for (i = 0; i < len - 1; i++)
    {
        if (s[i] == s[i+1])
        {
            dp[i][i+1] = 1;
            start = i;
            maxLen = 2;
        }
    }

    // when >=3
    for (k = 3; k <= len; k++)
    {

        // fix start index
        for (i = 0; i < len-k+1; i++)
        {
            // get the ending index
            j = i + k - 1;

            // if you do not know why is i+1,j-1,you can think delete head and tail,judge it is palindromic substring? this is a sub problem.
            if (dp[i+1][j-1] && s[i] == s[j])
            {
                dp[i][j] = 1;

                if (k >= maxLen)
                {
                    start = i;
                    maxLen = k;
                }
            }
        }
    }

    // for debug
    //printf("maxLen is %d\n",maxLen);
    // printf("start is %d\n",start);

    ret = calloc(1005,sizeof(char));
    int count = 0;
    // assign the from start and maxLen string  to the ret string.
    for (i = start; i < start + maxLen; i++)
    {

        ret[count] = s[i];
        count++;
    }

    return ret;
}
//第三种解法 中心扩展法
char* longestPalindrome(char* s)
{
    int len = strlen(s);
    int start = 0;
    int maxLen = 1;
    int i,j;
    int low,high;
    char *ret;
    for (i = 1; i < len; i++)
    {

        // even length
        low = i - 1;
        high = i;

        while (low >=0 && high < len && s[low] == s[high])
        {
            if (high - low + 1 >= maxLen)
            {
                start = low;
                maxLen = high - low + 1;
            }
            // expand the length
            low--;
            high++;
        }


        // odd length
        low = i - 1;
        high = i + 1;

        while (low >=0 && high < len && s[low] == s[high])
        {
            if (high - low + 1 >= maxLen)
            {
                start = low;
                maxLen = high - low + 1;
            }
            // expand the length
            low--;
            high++;
        }

    }


    ret = calloc(1005,sizeof(char));
    int count = 0;
    // assign the from start and maxLen string  to the ret string.
    for (j = start; j < start + maxLen; j++)
    {

        ret[count] = s[j];
        count++;
    }
    return ret;
}
//第四种 Manacher‘s Algorithm 马拉车算法
char* longestPalindrome(char* s)
{
    int N = strlen(s);
    if (N == 0) {
        return "";
    }
    if (N == 1) {
        return s;
    }

    N = 2 * N + 1;  // Position count
    int L[N];       // LPS Length Array
    L[0] = 0;
    L[1] = 1;
    int C = 1;      //centerPosition
    int R = 2;      //centerRightPosition
    int i = 0;      //currentRightPosition
    int iMirror;    //currentLeftPosition
    int expand = -1;
    int diff = -1;
    int maxLPSLength = 0;
    int maxLPSCenterPosition = 0;
    int start = -1;
    int end = -1;

    for (i = 2;i < N;i++) {
        iMirror = 2 * C - i;

        expand = 0;

        diff = R - i;

        if (diff > 0) {
            if (L[iMirror] < diff) {
                L[i] = L[iMirror];
            }else if (L[iMirror] == diff && i == N-1) {
                L[i] = L[iMirror];
            }else if (L[iMirror] == diff && i < N-1) {
                L[i] = L[iMirror];
                expand = 1;
            }else if (L[iMirror] > diff) {
                L[i] = diff;
                expand = 1;
            }
        }else {
            L[i] = 0;
            expand = 1;
        }

        if (expand == 1) {
            while ( (i + L[i]) < N && (i - L[i] > 0) && ( (i + L[i] + 1) %2 ==0 || (s[(i + L[i] + 1)/2]  == s[(i - L[i] - 1)/2] )) ) {
                L[i]++;
            }
        }

        if (L[i] >= maxLPSLength) {
            maxLPSLength = L[i];
            maxLPSCenterPosition = i;
        }

        if (i + L[i] > R) {
            C = i;
            R = i + L[i];
        }
    }
    start = (maxLPSCenterPosition - maxLPSLength) / 2;
    end = start + maxLPSLength - 1;

    char *ret;

    ret = calloc(1005,sizeof(char));
    int count = 0;
    int j;
    // assign the from start and maxLen string  to the ret string.
    for (j = start; j <= end; j++)
    {

        ret[count] = s[j];
        count++;
    }
    return ret;

}

发表评论

电子邮件地址不会被公开。 必填项已用*标注