longest common substring solution is for non-contiguous strings

[leshow]

https://en.wikipedia.org/wiki/Longest_common_substring_problem

according to wikipedia, because the substring is contiguous, we should end up with something like: (I don't know python, sorry)

// preamble omitted
  let mut res = 0;
  for i in 0..a.len()+1 {
    for j in 0..b.len()+1 {
      if i == 0 || j == 0 { dist[i][j] = 0; }
      else if a[i - 1] == b[j - 1] {
        dist[i][j] = 1 + dist[i - 1][j - 1];
        res = std::cmp::max(res, dist[i][j]);
      }
      else {
        dist[i][j] = 0;
      }
    }
  }

Other solutions I've found also do something similar: http://www.geeksforgeeks.org/longest-common-substring/

However, the longest common substring implemented here does:

# preamble omitted
        for i in range(num_rows):
            for j in range(num_cols):
                if i == 0 or j == 0:
                    T[i][j] = 0
                elif str0[j - 1] != str1[i - 1]:
                    T[i][j] = max(T[i][j - 1],
                                  T[i - 1][j])
                else:
                    T[i][j] = T[i - 1][j - 1] + 1

despite stating:

Is a substring a contiguous block of chars?
Yes

It looks as though the solution is modelling the recurrence relation for subsequence not substring. Have a look at the geeksforgeeks solution for subsequence:

http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/

It's very similar to this repo's implementation of 'substring'

[donnemartin]

Hi @leshow, good catch! You're right it seems to be implemented as longest common subsequence. Are you interested in making a pull request to change the existing challenge to properly label it as a subsequence?

---

For longest common substring, I think it would be more like below. This would be a new challenge.

...
elif str0[j - 1] != str1[i - 1]:
    T[i][j] = 0
...

[leshow]

Sure! I'll make the necessary changes to the answer.

Personally, I think the solution makes more sense when the containing if case tests for a match, a[i-1] == b[j-1], instead of doing the inequality test first, but I'll leave that the way it is.