Example: Longest Common Substring - rFronteddu/general_wiki GitHub Wiki

You are given 2 string are are tasked to find the longest common substring (consecutive characters)

---	---	a	b	c	d	a	f
---	0	0	0	0	0	0	0
g	0	0	0	0	0	0	0
b	0	0	1	0	0	0	0
c	0	0	0	2	0	0	0
d	0	0	0	0	3	0	0
f	0	0	0	0	0	0	1

lcSubstring(x, y)
    let d[0..x.len, 0..y.len] be a 2D array initialized to 0
    maxI = 0
    maxJ = 0
    
    // we will use i-1 and j-1 to access x and y
    for i = 1 to x.len
        for j = 1 to y.len
            // if they are different we set zero because elements have to be consecutive
            if x[i-1] == y[j-1]  
                // if they are same we consider the len of the subsequence without the two 
                d[i,j] = 1 + d[i-1,j-1] 
                if d[i,j] > d[maxI, maxJ]
                    maxI = i
                    maxJ = j

    // array of selected elements
    sel = []
    i = maxI
    j = maxJ
    while d[i,j] != 0 
        // insert to head
        sel.insert(0, x[i-1])
        i--
        j--
    return sel