回文字符串(Palindromic_String)「建议收藏」

回文字符串(Palindromic_String)「建议收藏」一、基本概念回文字符串:是一个正读和反读都一样的字符串。二、问题与算法(1)判断思想:1、初始化标志flag=true;2、输入字符串str,并获取其长度len;3、定义并初始化游标i=0,j=len-1,分别指向字符串开头和末尾;4、比较字符str[i]和str[j],若i==j,转至7,否则往下执行5;5、若str[i]和str[j]相等...

一、基本概念

回文字符串:是一个正读和反读都一样的字符串。

 

 

 

二、问题与算法

(1)判断

思想:

1、初始化标志flag=true;

2、输入字符串str,并获取其长度len;

3、定义并初始化游标i=0,j=len-1,分别指向字符串开头和末尾;

4、比较字符str[i]和str[j],若i==j,转至7,否则往下执行5;

5、若str[i]和str[j]相等,则游标i加1,游标j减1后转至4,否则往下执行6;

6、令标志位flag=flase,结束比较,str不是回文串,算法结束。

7、若str[i]和str[j]相等,结束比较,flag=true,str为回文串,算法结束。

 C++版本一

#include <stdio.h>
#include <string.h>

int main()
{
    char a[100]= {0};
    int i = 0;
    int len = 0;
    gets(a);
    len = strlen(a); //计算输入字符串的长度;
    for(i = 0; i < (len / 2); i++) //只需要判断前一半(len/2)长度就好了
    { 
        if(a[i] != a[len - 1 - i]) //判断是否为回文数;
        {
        printf("不是回文数\n");
        return 0;
        }
    }
    printf("是回文数\n");
    return 0;
}
只听到从架构师办公室传来架构君的声音:
樽罍饮散长亭暮。有谁来对上联或下联?

(2)最长回文子串(Longest_Palindromic_Substring)

1、朴素

思想:

1)从最长的子串开始,遍历所有该原字符串的子串;

2)每找出一个字符串,就判断该字符串是否为回文;

3)子串为回文时,则找到了最长的回文子串,因此结束;反之,则继续遍历。

C++版本一

此代码由Java架构师必看网-架构君整理
/* * 判断str[i...j]是否是回文串 */ bool isPalindrome(const char *str, int begin, int end) { while (begin <= end) { if (str[begin] == str[end]) { begin++; end--; } else return false; } return true; } /* *返回字符串str的最长回文子串的长度 */ int longestPalindrome(const char *str) { if (str == NULL) return 0; int len = strlen(str); if (len == 1) return 1; int longest = 1; for (int i = 0; i < len; i++) for (int j = i + 1; j < len; j++) if (isPalindrome(str, i, j) == true) longest = longest < j - i + 1 ? j - i + 1 : longest; return longest; }

JAVA版本一

 public static String longestPalindrome(String s) {
        if(s.length() <= 1)
            return s;
        for(int i = s.length();i > 0; i--) {//子串长度
            for (int j = 0; j <= s.length() - i; j++) {
                String sub = s.substring(j , i + j);//子串位置
                int count = 0;//计数,用来判断是否对称
                for (int k = 0; k < sub.length() / 2; k++) {//左右对称判断
                    if (sub.charAt(k) == sub.charAt(sub.length() - k - 1))
                        count++;
                }
                if (count == sub.length() / 2)
                    return sub;
            }
        }
        return "";//表示字符串中无回文子串

    }

2、中心扩散

思想:

1)将子串分为单核和双核的情况,单核即指子串长度为奇数,双核则为偶数;

2)遍历每个除最后一个位置的字符index(字符位置),单核:初始low = 初始high = index,low和high均不超过原字符串的下限和上限;判断low和high处的字符是否相等,相等则low++、high++(双核:初始high = 初始low+1 = index + 1);

3)每次low与high处的字符相等时,都将当前最长的回文子串长度与high-low+1比较。后者大时,将最长的回文子串改为low与high之间的;

4)重复执行2)、3),直至high-low+1 等于原字符串长度或者遍历到最后一个字符,取当前截取到的回文子串,该子串即为最长的回文子串。
 

 

C++版本一

此代码由Java架构师必看网-架构君整理
string longestPalindrome(string s) { if(s.empty()) return ""; if(s.size()==1) return s; int start=0,maxlength=1;//记录最大回文子串的起始位置以及长度 for(int i=0;i<s.size();i++) for(int j=i+1;j<s.size();j++)//从当前位置的下一个开始算 { int temp1,temp2; for(temp1=i,temp2=j;temp1<temp2;temp1++,temp2--) { if(s[temp1]!=s[temp2]) break; } if(temp1>=temp2 && j-i+1>maxlength)//这里要注意条件为temp1>=temp2,因为如果是偶数个字符,相邻的两个经上一步会出现大于的情况 { maxlength = j-i+1; start=i; } } return s.substr(start,maxlength);//利用string中的substr函数来返回相应的子串,第一个参数是起始位置,第二个参数是字符个数 }

JAVA版本一

private static int maxLen = 0;

private static String sub = "";

public static String longestPalindrome(String s) {
        if(s.length() <= 1)
            return s;

        for(int i = 0;i < s.length()-1;i++){

            findLongestPalindrome(s,i,i);//单核回文

            findLongestPalindrome(s,i,i+1);//双核回文
        }
        return sub;
    }
    public static  void findLongestPalindrome(String s,int low,int high){
        while (low >= 0 && high <= s.length()-1){
            if(s.charAt(low) == s.charAt(high)){
                if(high - low + 1 > maxLen){
                    maxLen = high - low + 1;
                    sub = s.substring(low , high+1);
                }
                low --;//向两边扩散找当前字符为中心的最大回文子串
                high ++;
            }
            else
                break;
        }
    }

3、动态规划

思想:

 对于字符串str,假设dp[i,j]=1表示str[i...j]是回文子串,那个必定存在dp[i+1,j-1]=1。这样最长回文子串就能分解成一系列子问题,可以利用动态规划求解了。

首先构造状态转移方程

回文字符串(Palindromic_String)「建议收藏」

 

上面的状态转移方程表示,当str[i]=str[j]时,如果str[i+1...j-1]是回文串,则str[i...j]也是回文串;如果str[i+1...j-1]不是回文串,则str[i...j]不是回文串。

初始状态

  • dp[i][i]=1

  • dp[i][i+1]=1 if str[i]==str[i+1]

上式的意义是单个字符,两个相同字符都是回文串。

 

C++版本一

int dp[1005][1005];
    string longestPalindrome(string& s) {
        // Write your code here
        O(n^2)
        int len = s.size();
        memset(dp, 0, sizeof(dp));
        for(int i=0; i<len; ++i)
            dp[i][1] = 1;
        int ld=0, rd=0, maxL = 1;
        for(int k=2; k<=len; ++k){
            for(int i=0, j; i<len && (j=i+k-1)<len; ++i){
                if(s[i] == s[j] && dp[i+1][k-2] == k-2)
                        dp[i][k] = dp[i+1][k-2] + 2;
                else 
                    dp[i][k] = max(dp[i+1][k-1], dp[i][k-1]);
                if(maxL<dp[i][k]){
                    maxL = dp[i][k];
                    ld = i;
                    rd = j;
                }
            }
        }
        return s.substr(ld, rd-ld+1);
    }

C++版本二

/*
*返回字符串str的最长回文子串的长度
*/
int longestPalindrome(const char *str)
{
    if (str == NULL) return 0;
    int len = strlen(str);
    if (len == 1)return 1;
    int longest = 1;
    int dp[100][100];
    for (int i = 0; i < len; i++)
    {
        dp[i][i] = 1;
        if (str[i] == str[i + 1])
            dp[i][i + 1] = 1;
    }

    for (int i = 0; i < len; i++)
    {
        for (int j = i + 2; j <= len; j++)
        {
            if (str[i] == str[j])
            {
                dp[i][j] = dp[i][j - 1];
                if (dp[i][j] == 1)
                {
                    int tmp = j - i + 1;
                    if (longest < tmp)longest = tmp;
                }
            }
            else dp[i][j] = 0;
        }
    }
    return longest;
}

动态规划

JAVA版本一

package com.ysw.test;

import java.util.Scanner;

/*
 * 问题描述:
 * 给定一个字符串S,找出它的最大的回文子串,你可以假设字符串的最大长度是1000,
 * 而且存在唯一的最长回文子串 。
 */
public class LongestPalindrome {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // 从键盘读入字符串
        String str = null;
        Scanner reader = new Scanner(System.in);
        str = reader.nextLine();
        System.out.println(getLongestPalindrome(str));
    }

    /**
     * 此方法返回s的最长回文串
     * 
     * @param str
     * @return
     */
    private static String getLongestPalindrome(String str) {

        boolean dp[][];
        // 如果字符串的长度为0,则认为str的最长回文串为空字符串
        if (str.length() == 0) {
            return "";
        }
        // 字符串str长度为1.则字符串本身就是一个最长回文串
        if (str.length() == 1) {
            return str;
        }
        // dp[i][j],表示字符串str从str[i]到str[j]的子串为最长回文子串
        dp = new boolean[str.length()][str.length()];
        // 记录已经找到的最长回文子串的长度
        int maxLen = 1;
        // 记录最长回文子串的起点位置和终点位置
        int start = 0, end = 0;
        // 动态规划的进行是按照字符串的长度从1 到 n推进的,k表示正在判断的子串的长度
        // 用于和已知的子串的长度maxLen进行比较
        int k;
        // 找出str的所有子串的dp对应的boolean值,初始化过程
        for (int i = 0; i < str.length(); i++) {
            for (int j = 0; j < str.length(); j++) {
                // 当i==j的时候,只有一个字符的字符串
                // 当i>j的时候认为是空串,dp[i][j]
                if (i >= j) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = false;
                }
            }
        }

        // 我在这里犯了一个幼稚的错误,把i、j的定义放在了for循环中,在else{}中是访问不到的
        // 运行程序报java.lang.StringIndexOutOfBoundsException: String index out of
        // range错误
        int i, j;
        for (k = 1; k < str.length(); k++) {
            for (i = 0; i + k < str.length(); i++) {

                j = i + k;
                if (str.charAt(i) != str.charAt(j)) {
                    dp[i][j] = false;
                } else {
                    dp[i][j] = dp[i + 1][j - 1];
                    if (dp[i][j]) {
                        // 判断找到的子串的长度是否大于我们已知的最长子串的长度
                        if (k + 1 > maxLen) {
                            // 记录最长回文子串
                            maxLen = k + 1;
                            // 记录子串的起始位置,因为后面的函数subString(int beginIndex,int
                            // endIndex)函数要用到
                            start = i;
                            end = j;
                        }
                    }
                }
            }
        }
        return str.substring(start, end + 1);
    }
}

4、Manacher's Algorithm(马拉车算法)

思想:

 

一)第一步是改造字符串S,变为T,其改造的方法如下:

在字符串S的字符之间和S的首尾都插入一个“#”,如:S=“abba”变为T="#a#b#b#a#" 。我们会发现S的长度是4,而T的长度为9,长度变为奇数了!!那S的长度为奇数的情况时,变化后的长度还是奇数吗?我们举个例子,S=“abcba”,变化为T=“#a#b#c#b#a#”,T的长度为11,所以我们发现其改造的目的是将字符串的长度变为奇数,这样就可以统一的处理奇偶的情况了

二)第二步,为了改进回文相互重叠的情况,我们将改造完后的T[ i ] 处的回文半径存储到数组P[ ]中,P[ i ]为新字符串T的T[ i ]处的回文半径,表示以字符T[i]为中心的最长回文字串的最端右字符到T[i]的长度,如以T[ i ]为中心的最长回文子串的为T[ l, r ],那么P[ i ]=r-i+1。这样最后遍历数组P[ ],取其中最大值即可。若P[ i ]=1表示该回文串就是T[ i  ]本身。举一个简单的例子感受一下:

回文字符串(Palindromic_String)「建议收藏」

数组P有一性质,P[ i ]-1就是该回文子串在原字符串S中的长度 ,那就是P[i]-1就是该回文子串在原字符串S中的长度,至于证明,首先在转换得到的字符串T中,所有的回文字串的长度都为奇数,那么对于以T[i]为中心的最长回文字串,其长度就为2*P[i]-1,经过观察可知,T中所有的回文子串,其中分隔符的数量一定比其他字符的数量多1,也就是有P[i]个分隔符,剩下P[i]-1个字符来自原字符串,所以该回文串在原字符串中的长度就为P[i]-1。【这段解释引用 dyx心心

另外,由于第一个和最后一个字符都是#号,且也需要搜索回文,为了防止越界,我们还需要在首尾再加上非#号字符,实际操作时我们只需给开头加上个非#号字符,结尾不用加的原因是字符串的结尾标识为'\0',等于默认加过了。这样原问题就转化成如何求数组P[ ]的问题了。

三)如何求数组P [ ]

  从左往右计算数组P[ ], Mi为之前取得最大回文串的中心位置,而R是最大回文串能到达的最右端的值。

  1)当 i <=R时,如何计算 P[ i ]的值了?毫无疑问的是数组P中点 i 之前点对应的值都已经计算出来了。利用回文串的特性,我们找到点 i 关于 Mi 的对称点 j ,其值为 j= 2*Mi-i 。因,点 j 、i 在以Mi 为中心的最大回文串的范围内([L ,R]),

       a)那么如果P[j] <R-i (同样是L和j 之间的距离),说明,以点 j 为中心的回文串没有超出范围[L ,R],由回文串的特性可知,从左右两端向Mi遍历,两端对应的字符都是相等的。所以P[ j ]=P[ i ](这里得先从点j转到点i 的情况),如下图:

 

回文字符串(Palindromic_String)「建议收藏」

     b)如果P[ j ]>=R-i (即 j 为中心的回文串的最左端超过 L),如下图所示。即,以点 j为中心的最大回文串的范围已经超出了范围[L ,R] ,这种情况,等式P[ j ]=P[ i ]还成立吗?显然不总是成立的!因,以点 j 为中心的回文串的最左端超过L,那么在[ L, j ]之间的字符肯定能在( j, Mi ]找到相等的,由回文串的特性可知,P[ i ] 至少等于R- i,至于是否大于R-i(图中红色的部分),我们还要从R+1开始一一的匹配,直达失配为止,从而更新R和对应的Mi以及P[ i ]。

回文字符串(Palindromic_String)「建议收藏」

  2)当 i > R时,如下图。这种情况,没法利用到回文串的特性,只能老老实实的一步步去匹配。

回文字符串(Palindromic_String)「建议收藏」

C++版本一

 

string Manacher(string s)
{
    /*改造字符串*/
    string res="$#";
    for(int i=0;i<s.size();++i)
    {
        res+=s[i];
        res+="#";
    }

    /*数组*/
    vector<int> P(res.size(),0);
    int mi=0,right=0;   //mi为最大回文串对应的中心点,right为该回文串能达到的最右端的值
    int maxLen=0,maxPoint=0;    //maxLen为最大回文串的长度,maxPoint为记录中心点

    for(int i=1;i<res.size();++i)
    {
        P[i]=right>i ?min(P[2*mi-i],right-i):1;     //关键句,文中对这句以详细讲解
        
        while(res[i+P[i]]==res[i-P[i]])
            ++P[i];
        
        if(right<i+P[i])    //超过之前的最右端,则改变中心点和对应的最右端
        {
            right=i+P[i];
            mi=i;
        }

        if(maxLen<P[i])     //更新最大回文串的长度,并记下此时的点
        {
            maxLen=P[i];
            maxPoint=i;
        }
    }
    return s.substr((maxPoint-maxLen)/2,maxLen-1);
}

JAVA版本一

public String longestPalindrome(String s) {
        List<Character> s_new = new ArrayList<>();
        for(int i = 0;i < s.length();i++){
            s_new.add('#');
            s_new.add(s.charAt(i));
        }
        s_new.add('#');
        List<Integer> Len = new ArrayList<>();
        String sub = "";//最长回文子串
        int sub_midd = 0;//表示在i之前所得到的Len数组中的最大值所在位置
        int sub_side = 0;//表示以sub_midd为中心的最长回文子串的最右端在S_new中的位置
        Len.add(1);
        for(int i = 1;i < s_new.size();i++){
            if(i < sub_side) {//i < sub_side时,在Len[j]和sub_side - i中取最小值,省去了j的判断
                int j = 2 * sub_midd - i;
                if(j >= 2 * sub_midd - sub_side &&  Len.get(j) <= sub_side - i){
                    Len.add(Len.get(j));
                }
                else
                    Len.add(sub_side - i + 1);
            }
            else//i >= sub_side时,从头开始匹配
                Len.add(1);
            while( (i - Len.get(i) >= 0 && i + Len.get(i) < s_new.size()) && (s_new.get(i - Len.get(i)) == s_new.get(i + Len.get(i))))
                Len.set(i,Len.get(i) + 1);//s_new[i]两端开始扩展匹配,直到匹配失败时停止
            if(Len.get(i) >= Len.get(sub_midd)){//匹配的新回文子串长度大于原有的长度
                sub_side = Len.get(i) + i - 1;
                sub_midd = i;
            }
        }
        sub = s.substring((2*sub_midd - sub_side)/2,sub_side /2);//在s中找到最长回文子串的位置
        return sub;

    }

三、例题

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4110(题解:https://blog.csdn.net/weixin_43272781/article/details/89645047

四、参考文章

https://baike.baidu.com/item/%E5%9B%9E%E6%96%87%E4%B8%B2/1274921?fr=aladdin

https://blog.csdn.net/it_liy/article/details/78680786

https://blog.csdn.net/qq_32354501/article/details/80084325

https://www.cnblogs.com/love-yh/p/7072161.html

https://www.cnblogs.com/mini-coconut/p/9074315.html

https://www.cnblogs.com/ysw-go/p/5873350.html

本文来源Starzkg,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/210154
0
   

发表评论