PythonQuestion on Longest Common Substring(LCS) algorithm
<p>I'm pretty new to Python, it's my first  programming language, and I've wanted to work on some manual data structure manipulation and playing around.</p>

<p>I've recently been learning the basic algorithm for solving the LCS problem, and I understand how it works besides one line of code that I for some weird reason can't seem to convince myself I am grasping entirely.</p>

<p>this is the code I've been using to learn from after I couldn't get it down myself quite right.</p>

<p>EDIT 2: <strong>Anyway to make this work with an input of two lists of integers?**I figured out that I was understanding my original question correctly, but would anyone know how I could make this work with a **list</strong> of integers? I tried converting S and T to a string of comma separated values, which worked in matching some of the characters, but even then it rarely worked in most test-cases. I'm not sure why it wouldn't, as it is still just two strings being compared, but with commas. </p>

<pre><code>def lcs(S,T):
    m = len(S)
    n = len(T)
    counter = [[0]*(n+1) for x in range(m+1)]
    longest = 0
    lcs_set = set()
    for i in range(m):
        for j in range(n):
            if S[i] == T[j]:
                c = counter[i][j] + 1
                counter[i+1][j+1] = c
                if c &gt; longest:
                    lcs_set = set()
                    longest = c
                    lcs_set.add(S[i-c+1:i+1])
                elif c == longest:
                    lcs_set.add(S[i-c+1:i+1])

    return lcs_set
</code></pre>

<p>Now my issue is understanding is the line : lcs_set.add(S[i-c+1:i-1])</p>

<p>I understand that the counter is incremented when a match is found, to give <em>longest</em> the length of the substring. So, to make it easy, if S = Crow and T = Crown, when you reach w, the last match, the <em>counter</em> is incremented to 4, and i is at index 3 of S.</p>

<p>Does this mean I am to read this as: i (index3 on S, the W) - c (4), so 3-4 = -1, so 3-4+1 = 0 (at C) and for the right side of the slice: i(3) + 1 = 4(N, but will not be included, obviously), meaning we end with S[0:4], Crow, to <em>LCS_Set</em>?</p>

<p>If that is the case, I guess I am confused as to why we are adding the whole substring to the set, and not just the newest matched character? </p>

<p>If I understand right, it is updating <em>LCS_set</em> with the entire slice of the current matched substring, so if it were on the second match, R, the <em>counter</em> would be at 2, i would be at 1, and it would be saying S[1-2+1:i(1)+1], so 1-2 = -1, -1 + 1 = 0(C) up to i(1)+1 = 2 (leaving us with S[0:2], or CR), so each time around, the set is updated with the entire substring, and not just the current index. </p>

<p>It's not really a problem, I just want to make sure I'm understanding this correctly.</p>

<p>I would really appreciate any input, or any tips anyone might see with my current logic!!</p>

<p>EDIT:</p>

<p>I just realized I was totally forgetting that the position at C is the current counter number, therefore it obviously wouldn't be updating the LCS_set with the current max match number, and it can't update it with just the current matched letter, so it has to take the slice of the substring in order to update the LCS_Set. 
Thanks in advance!</p>