Answer to Question 4(d)
Practice Questions for Exam 4

  longestCommonSubstring(x1… xn, y1… ym)
    L = new int[0..n, 0..m]
    S = new int[0..n, 0..m]
    for i = 0, ..., n
      L[i,0] = 0
      S[i,0] = 0

    for j = 0, ..., m
      L[0,j] = 0
      S[0,j] = 0

    for i = 1, ..., n
      for j = 1, ..., m
        if xi = yj
          S[i,j] = 1 + S[i-1,j-1]
          L[i,j] = max(S[i,j], L[i-1,j], L[i,j-1])
        else
          S[i,j] = 0
          L[i,j] = max(L[i-1,j], L[i,j-1])

    return L[n,m]