最长重复子串

给你一个字符串 s ，考虑其所有 重复子串 ：即 s 的（连续）子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。

返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串，那么答案为 "" 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-duplicate-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

对应的答案区间为[0,n],二分每一个答案mid,通过O(n)时间复杂度判断是否成立

class Solution {
    String res="";
    public String longestDupSubstring(String s) {
        //通过二分答案的方式
        int left=0;
        int right=s.length();
        while(left<right){
            int mid=left+right+1>>1;
            if(check(s,mid)){
                left=mid;
            }else{
                right=mid-1;
            }

        }
        return res;
    }
    public boolean check(String s,int len){
        Set<String> set=new HashSet<>();
        for(int i=0;i+len-1<s.length();i++){
            int j=i+len-1;
            String substr=s.substring(i,j+1);
            if(set.contains(substr)){
                res=substr;
                return true;
            }
            set.add(substr);
        }
        return false;
    }
}

超过内存限制 set[HTML_REMOVED]----->set[HTML_REMOVED] 通过字符串hash进行字符串到整数的映射

class Solution {
    String res="";
    long[] p;long[] h;
    public String longestDupSubstring(String s) {

        //字符串哈hash
        p=new long[s.length()+10];
        h=new long[s.length()+10];
        p[0]=1;
        for(int i=1;i<=s.length();i++){
            p[i]=p[i-1]*13331;
            h[i]=h[i-1]*13331+s.charAt(i-1)-'a'+1;
        }

        //通过二分答案的方式
        int left=0;
        int right=s.length();
        while(left<right){
            int mid=left+right+1>>1;
            if(check(s,mid)){
                left=mid;
            }else{
                right=mid-1;
            }

        }
        return res;
    }

    public boolean check(String s,int len){
        Set<Long> set=new HashSet<>();
        for(int i=1;i+len-1<=s.length();i++){
            int j=i+len-1;
            long value=h[j]-h[i-1]*p[j-i+1];
            if(set.contains(value)){
                res=s.substring(i-1,j);
                return true;
            }
            //将对应的hash值放入集合
            set.add(value);
        }
        return false;
    }

    // public boolean check(String s,int len){
    //     Set<String> set=new HashSet<>();
    //     for(int i=0;i+len-1<s.length();i++){
    //         int j=i+len-1;
    //         String substr=s.substring(i,j+1);
    //         if(set.contains(substr)){
    //             res=substr;
    //             return true;
    //         }
    //         set.add(substr);
    //     }
    //     return false;
    // }
}

最长回文前缀子串 求字符串最长回文子串前缀

class Solution {
    public String shortestPalindrome(String s) {
        if(s.length()==0){
            return s;
        }
        int n=s.length();
        int left=0;int right=0;
        int p=131;int mul=1;
        int index=0;
        for(int i=0;i<n;i++){//对于任意一个前缀字符串  
            left=left*p+s.charAt(i)-'a'+1;
            right=right+(s.charAt(i)-'a'+1)*mul;
            mul=mul*p;
            if(left==right){//如果该前缀为回文串  记录最长的前缀回文
                index=i;
            }
        }
        return (new StringBuilder(s.substring(index+1))).reverse().toString()+s;
    }
}

最长回文子序列

定义dp[i][j]表示区间s[i:j]最长回文子串
if(s[i]==s[j]){
dp[i][j]=dp[i+1][j-1]+2;
}else{
dp[i][j]=max(dp[i][j-1],dp[i+1][j]);
}
循环顺序

public static void main(String[] args) {
        //最长回文子序列
        String s="dabca";
        int n=s.length();
        int[][] dp=new int[n][n];
        for(int i=n-1;i>=0;i--){
            dp[i][i]=1;
            for(int j=i+1;j<n;j++){
                if(s.charAt(i)==s.charAt(j)){
                    dp[i][j]=dp[i+1][j-1]+2;
                }else{
                    dp[i][j]=Math.max(dp[i][j-1],dp[i+1][j]);
                }
            }
        }
        System.out.println(dp[0][n-1]);
    }

字符串最长回文子序列 变体

一个字符串，最少添加多少字符，使得该字符串成为回文字符串

结论：对于一个字符串的回文子序列 回文中心 一定是该字符串自身的字符（奇数长度和偶数长度的回文子序列）

class Solution {
    public int minInsertions(String s) {
        int n=s.length();
        if(n==1){
            return 0;
        }
        int[][] dp=new int[n][n];
        for(int i=n-1;i>=0;i--){
            for(int j=i+1;j<n;j++){
                dp[i][i]=1;
                if(s.charAt(i)==s.charAt(j)){
                    dp[i][j]=dp[i+1][j-1]+2;
                }else{
                    dp[i][j]=Math.max(dp[i][j-1],dp[i+1][j]);
                }
            }
        }
        return n-dp[0][n-1];
    }
}

区间dp

dp[i][j]表示区间s[i:j]内字符串需要添加dp[i][j]次使得该字符串成为回文字符串

public int minInsertions(String s) {
        int n=s.length();
        //区间dp
        int[][] dp=new int[n][n];
        for(int len=2;len<=n;len++){
            for(int i=0;i+len-1<n;i++){
                int j=i+len-1;
                dp[i][j]=Math.min(dp[i+1][j],dp[i][j-1])+1;
                if(s.charAt(i)==s.charAt(j)){
                    dp[i][j]=Math.min(dp[i][j],dp[i+1][j-1]);
                }
            }
        }
        return dp[0][n-1];
    }