首页 > 编程 > C > 正文

关于最大对称字符串的算法

2020-02-24 14:35:11
字体:
来源:转载
供稿:网友

抓住2018年的尾巴,我们的学习不能止步,本文将给大家讲述的是关于最大对称字符串的算法,需要的朋友可以参考下其中的内容详情。

算法一:O(n^3)

判断字串是否对称是从外到里, O(n)

 


#include
#include

 

/*
 *判断起始指针,到结束指针的字符串是否对称
 */
int IsSymmetrical(char* pBegin, char* pEnd)
{
    if(pBegin == NULL || pEnd == NULL || pBegin > pEnd)
    return 0;

    while(pBegin     {
    if(*pBegin != *pEnd)
        return 0;
    pBegin++;
    pEnd--;
    }
    return 1;
}

/*
 *查找最大对称字串长度,时间复杂度是O(n^3)
 */
int GetLongestSymmetricalLength(char* pString)
{
    if(pString == NULL)
    return 0;
    int symmetricalLength = 1;
    char* pFirst = pString;
    int length = strlen(pString);

    while(pFirst     {
    char* pLast = pFirst + 1;
    while(pLast     {
        if(IsSymmetrical(pFirst, pLast))
        {
        int newLength = pLast - pFirst + 1;
        if(newLength > symmetricalLength)
            symmetricalLength = newLength;
        }
        pLast++;
    }
    pFirst++;
    }
    return symmetricalLength;
}

int main()
{
    char* str = "google";
    int len = GetLongestSymmetricalLength(str);
    printf("%d", len);
    return 0;
}


算法2: O(n^2)

 

判断字串是否对称是从外到里, O(1)

 


#include
#include

 


int GetLongestSymmetricalLength(char* pString)
{
    if(pString == NULL)
    return 0;
    int symmetricalLength = 1;

    char* pChar = pString;
    while(*pChar != '/0')
    {
    //奇数长度对称, 如 aAa
    char* left = pChar - 1;
    char* right = pChar + 1;
    while(left >= pString && *right != '/0' && *left==*right)
    {
        left--;
        right++;
    }
    int newLength = right - left - 1;   //退出循环是*left!=*right
    if(newLength > symmetricalLength)
        symmetricalLength = newLength;

    //偶数长度对称, 如 aAAa
    left = pChar;
    right = pChar + 1;
    while(left >= pString && *right != '/0' && *left==*right)
    {
        left--;
        right++;
    }
    newLength = right - left - 1;   //退出循环是*left!=*right
    if(newLength > symmetricalLength)
        symmetricalLength = newLength;

    pChar++;
    }

    return symmetricalLength;
}

int main()
{
    char* str = "google";
    int len = GetLongestSymmetricalLength(str);
    printf("%d", len);
    return 0;
}

 

算法3:manacher算法

 原串:abaab
新串:#a#b#a#a#b#
这样一来,原来的奇数长度回文串还是奇数长度,偶数长度的也变成以‘#'为中心的奇数回文串了。
接下来就是算法的中心思想,用一个辅助数组P记录以每个字符为中心的最长回文半径,也就是P[i]记录以Str[i]字符为中心的最长回文串半径。P[i]最小为1,此时回文串为Str[i]本身。
我们可以对上述例子写出其P数组,如下
新串: # a # b # a # a # b #
P[]  :  1 2 1 4 1 2 5 2 1 2 1
我们可以证明P[i]-1就是以Str[i]为中心的回文串在原串当中的长度。
证明:
1、显然L=2*P[i]-1即为新串中以Str[i]为中心最长回文串长度。
2、以Str[i]为中心的回文串一定是以#开头和结尾的,例如“#b#b#”或“#b#a#b#”所以L减去最前或者最后的‘#'字符就是原串中长度的二倍,即原串长度为(L-1)/2,化简的P[i]-1。得证。

注: 不是很懂, 自己改了

 


#include
#include

 

int GetLongestSymmetricalLength(char* pString)
{
    int length = strlen(pString);
    char* pNewString = malloc(2*length+2);
    int i;
    for(i=0; i    {
    *(pNewString+i*2) = '#';
    *(pNewString+i*2+1) = *(pString+i);
    }
    *(pNewString+2*length) = '#';
    *(pNewString+2*length+1) = '/0';

    printf("%s/n", pNewString);
    int maxLength = 1;
    char* pChar;
    for(i=0; i    {
    int newLength = 1;
    pChar = pNewString + i;
    char* left = pChar-1;
    char* right = pChar+1;
    while(left>=pNewString && *right!='/0'&& *left==*right)
    {
        left--;
        right++;
        newLength++;
    }
    if(newLength > maxLength)
        maxLength = newLength;
    }

    return maxLength-1;
}

int main()
{
    char* str = "google";
    int len = GetLongestSymmetricalLength(str);
    printf("%d", len);
    return 0;
}

以上就是关于最大对称字符串的算法,想必都已有了一定的了解,更多相关内容请继续关注武林技术频道。

发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表

图片精选