Longest Common Substring

Question

We have two strings a and b respectively. The length of a is greater than or equal to b. We have to find out the longest common substring. If there are multiple answers then we have to output the substring which comes earlier in b (earlier as in whose starting index comes first).

Note: The length of a and b can be up to 10⁶.

I tried to find the longest common substring using suffix array (sorting the suffixes using quicksort). For the case when there is more than one answer, I tried pushing all the common substrings in a stack which are equal to the length of the longest common substring.

I wanted to know is there any faster way to do so?

Answer 1

Build a suffix tree of a string a$b, that is, a concatenated with some character like $ not occurring in both strings, then concatenated with b. A (compressed) suffix tree can be built in O(|a|+|b|) time and memory, and have O(|a|+|b|) nodes.

Now, for each node, we know its depth (the length of the string obtained by starting from the root and traversing the tree down to that node). We also can keep track of two boolean quantities: whether this node was visited during the build phase corresponding to a, and whether it was visited during the build phase corresponding to b (for example, we might as well build the two trees separately and then merge them using pre-order traversal). Now, the task boils down to finding the deepest vertex which was visited during both phases, which can be done by a single pre-order traversal. The case of multiple answers should be easy to handle.

This Wikipedia page contains another (brief) overview of the technique.

Answer 2

This is longest substring,what you are looking for is it with repetition or without . please go through this it might be helpful. http://www.programcreek.com/2013/02/leetcode-longest-substring-without-repeating-characters-java/

Answer 3

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)

Answer 4

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