1

我们有两个字符串a和b分别。的长度a大于或等于b。我们必须找出最长的公共子串。如果有多个答案，那么我们必须输出较早出现的子字符串b（早于其起始索引在前）。

注意：a和的长度b最大为 10 6。

我尝试使用后缀数组查找最长的公共子字符串（使用快速排序对后缀进行排序）。对于有多个答案的情况，我尝试将所有公共子字符串推入堆栈中，这些子字符串等于最长公共子字符串的长度。

我想知道有没有更快的方法呢？

4

4 回答 4

3

构建一个string的后缀树a$b，即a与一些字符连接，例如$两个字符串中都没有出现，然后与 连接b。一个（压缩的）后缀树可以在 O(|a|+|b|) 时间和内存中构建，并具有 O(|a|+|b|) 个节点。

现在，对于每个节点，我们知道它的深度（从根开始遍历树到该节点所获得的字符串的长度）。我们还可以跟踪两个布尔量：该节点是否在对应的构建阶段a被访问，以及在对应的构建阶段是否被访问b（例如，我们不妨分别构建两棵树，然后将它们合并使用前序遍历）。现在，任务归结为找到在两个阶段都访问过的最深顶点，这可以通过单个前序遍历来完成。多个答案的情况应该很容易处理。

此Wikipedia 页面包含该技术的另一个（简要）概述。

于 2014-03-11T08:44:35.600 回答
0

这是最长的子字符串，您正在寻找的是重复或不重复。请仔细阅读它可能会有所帮助。 http://www.programcreek.com/2013/02/leetcode-longest-substring-without-repeating-characters-java/

于 2014-05-17T18:37:20.297 回答
0 
import java.util.Scanner;
  public class JavaApplication8 {
      public static int find(String s1,String s2){
        int n = s1.length();
        int m = s2.length();
        int ans = 0;
        int[] a = new int[m];
        int b[] = new int[m];
        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                if(s1.charAt(i)==s2.charAt(j)){
                   if(i==0 || j==0 )a[j] = 1;
                   else{
                       a[j] = b[j-1] + 1;
                   }
                   ans = Math.max(ans, a[j]);
                }

            }
            int[] c = a;
            a = b;
            b = c;
        }
        return ans;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.next();
        String s2 = sc.next();
        System.out.println(find(s1,s2));
    }

}

Time Complexity O(N) Space Complexity O(N)

于 2018-04-11T17:39:00.453 回答
0 
package main

import (
    "fmt"
    "strings"
)

func main(){
    fmt.Println(lcs("CLCL","LCLC"))
}

func lcs(s1,s2 string)(max int,str string){
    str1 := strings.Split(s1,"")
    str2 := strings.Split(s2,"")
    fmt.Println(str1,str2)

    str = ""
    mnMatrix := [4][4]int{}
    for i:=0;i<len(str1);i++{
        for j:=0;j<len(str2);j++{
            if str1[i]==str2[j]{
                if i==0 || j==0 {
                    mnMatrix[i][j] = 1
                    max = 1
                    //str = str1[i]
                }else{
                    mnMatrix[i][j] = mnMatrix[i-1][j-1]+1
                    max = mnMatrix[i][j]
                    str = ""
                    for k:=max;k>=1;k--{
                        str = str + str2[k]
                        //fmt.Println(str)
                    }
                }


            }else{
                mnMatrix[i][j] = 0
            }
        }
    }
    fmt.Println(mnMatrix)
    return max, str
}

    enter code here
于 2020-03-22T16:07:44.877 回答