<reponame>shelper/leetcode<gh_stars>0
def longest_substr(str1, str2):
    dp = [[0] * (len(str1) + 1) for _ in range(len(str2) + 1)]
    res = 0
    for i, c1 in enumerate(str2):
        for j, c2 in enumerate(str1):
            p = 1 if c1 == c2 else 0
            dp[i + 1][j + 1] = dp[i][j] + p
            if dp[i + 1][j + 1] > res:
                ii, jj = i, j
                res = dp[i + 1][j + 1]

    print(ii, jj, res)


str1 = "abdabcd"
str2 = "ababcd"
longest_substr(str1, str2)

print(str1[5 - 4 : 5])


def longest_substr(str1, str2):
    dp = [[0] * (len(str1) + 1) for _ in range(len(str2) + 1)]
    res = 0
    for i, c1 in enumerate(str2):
        for j, c2 in enumerate(str1):
            p = 1 if c1 == c2 else 0
            dp[i + 1][j + 1] = dp[i][j] + p
            if dp[i + 1][j + 1] > res:
                ii, jj = i, j
                res = dp[i + 1][j + 1]

    print(ii, jj, res)


str1 = "abdabcd"
str2 = "ababcd"
longest_substr(str1, str2)

print(str1[5 - 4 : 5])