【编程题目】对称子字符串的最大长度 ★

旧城等待， 2022-03-31 09:45 179阅读 0赞

73.对称字符串的最大长度（字符串）。  
题目：输入一个字符串，输出该字符串中对称的子字符串的最大长度。  
比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出 4。

虽然知道会有简单的方法，可脑子就是转不动了，只好用最常见的，对所有可能的字符串判断是否为对称的。再输出最大长度 O(N3)

/*
    73.对称字符串的最大长度（字符串）。
    题目：输入一个字符串，输出该字符串中对称的子字符串的最大长度。
    比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出 4。
    */
    
    #include <stdio.h>
    #include <string.h>
    
    bool issymmetry(char * in, int len) //判断字符串是否对称
    {
        int i, j;
        for(i = 0, j = len - 1; i < j ; i++, j--)
        {
            if(in[i] != in[j])
            {
                return false;
            }
        }
        return true;
    }
    
    int maxSubSymLen(char * in, int len)
    {
        int nlen;
        for(nlen = len; nlen >= 1; nlen--) //按长度循环
        {
            if(nlen == 1)
            {
                return 1;
            }
            else
            {
                int i;
                for(i = 0; i <= len - nlen; i++) //首字母位置循环
                {
                    if(issymmetry(in + i, nlen))
                    {
                        for(int j = i; j < i + nlen; j++)
                        {
                            printf("%c ", in[j]);
                        }
                        return nlen;
                    }
                }
            }
        }
    }
    
    int main()
    {
        char a[40] = "asdgjoalsgjeslhfelgjdjglejf";
        int ans = maxSubSymLen(a, strlen(a));
        return 0;
    }

网上O（N2）解法是 长度从小向大循环

http://blog.163.com/clevertanglei900@126/blog/static/1113522592011912103756405/

如果我们换一种思路，我们从里向外来判断。也就是我们先判断子字符串A是不是对称的。如果A不是对称的，那么向该子字符串两端各延长一个字符得到的字符串肯定不是对称的。如果A对称，那么我们只需要判断A两端延长的一个字符是不是相等的，如果相等，则延长后的字符串是对称的。因此在知道A是否对称之后，只需要O（1）的时间就能知道aAa是不是对称的。

/*
    取得所有对称子串的最大长度
    时间复杂度： O(n^2)
    */
    
    int GetLongestSymmetricalLength(char* pString)
    {
        if(pString == NULL)
            return 0;
        int symmeticalLength = 1;
        char* pChar = pString;
        while(*pChar != '\0')
        {
            // Substrings with odd length
            char* left = pChar - 1;
            char* right = pChar + 1;
            while(left >= pString && *right != '\0' && *left == *right)
            {
                left--;
                right++;
            }
            int newLength = right - left - 1;    //退出while循环时，*left != *right
            if(newLength > symmeticalLength)
                symmeticalLength = newLength; 
    
            // Substrings with even length
            left = pChar;
            right = pChar + 1;
            while(left >= pString && *right != '\0' && *left == *right)
            {
                left--;
                right++;
    
            }
            newLength = right - left - 1;        //退出while循环时，*left != *right
            if(newLength > symmeticalLength)
                symmeticalLength = newLength;
            pChar++;
        }
        return symmeticalLength;
    }

居然还有O（N）的算法！！

http://blog.csdn.net/hackbuteer1/article/details/6686263

经常有一些题目围绕回文子串进行讨论，比如 HDOJ\_3068\_最长回文，求最长回文子串的长度。朴素算法是依次以每一个字符为中心向两侧进行扩展，显然这个复杂度是O(N^2)的，关于字符串的题目常用的算法有KMP、后缀数组、AC自动机，这道题目利用扩展KMP可以解答，其时间复杂度也很快O(N\*logN)。但是，今天笔者介绍一个专门针对回文子串的算法，其时间复杂度为O(n)，这就是manacher算法。  
大家都知道，求回文串时需要判断其奇偶性，也就是求aba和abba的算法略有差距。然而，这个算法做了一个简单的处理，很巧妙地把奇数长度回文串与偶数长度回文串统一考虑，也就是在每个相邻的字符之间插入一个分隔符，串的首尾也要加，当然这个分隔符不能再原串中出现，一般可以用‘\#’或者‘$’等字符。例如：  
原串：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。得证。  
依次从前往后求得P数组就可以了，这里用到了DP(动态规划)的思想，也就是求P\[i\]的时候，前面的P\[\]值已经得到了，我们利用回文串的特殊性质可以进行一个大大的优化。

#include <stdio.h>
    
    #define M 110010
    
    char b[M],a[M<<1];
    int p[M<<1];
    
    int Min(int a,int b)
    {
        return a<b?a:b;
    }
    
    int main(void)
    {
        int i,n,id,MaxL,MaxId;
        while(scanf("%s",&b[1])!=EOF)
        {
            MaxL=MaxId=0;
            for(i=1;b[i]!='\0';i++)
            {
                a[(i<<1)]=b[i];
                a[(i<<1)+1]='#';
            }
            a[0]='?';a[1]='#';
            n=(i<<1)+2;a[n]=0;
            MaxId=MaxL=0;
            for(i=1;i<n;i++)
            {
                if(MaxId>i)
                {
                    p[i]=Min(p[2*id-i],MaxId-i);
                }
                else
                {
                    p[i]=1;
                }
                while(a[i+p[i]]==a[i-p[i]])
                {
                    p[i]++;
                }
                if(p[i]+i>MaxId)
                {
                    MaxId=p[i]+i;
                    id=i;
                }
                if(p[i]>MaxL)
                {
                    MaxL=p[i];
                }
            }
            printf("%d\n",MaxL-1);
        }
        return 0;
    }