公共子串+变长窗口+动态规划 | HJ75 公共子串计算

# 最优解1（某字符为首的子串不再为公共子串时，首字符调换到下一个）
while True:
    try:
        a = input().upper()
        b = input().upper()
        n = 0
        for i in range(len(a)):
            if a[i-n:i+1] in b:  # 窗口尾端扩张1格，若也满足子串，子串长度n值加1，下一次窗口首端位置不变
                n += 1
        print(n)
    except:
        break

# 最优解2：动态规划
def solution(s1, s2):
    mxlen = 0
    dp = [[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)]    # 动态规划数组
    for i in range(len(s1)):
        for j in range(len(s2)): 
            if s1[i] == s2[j]:
                dp[i+1][j+1] = dp[i][j] + 1
                if dp[i+1][j+1] > mxlen:
                    mxlen = dp[i+1][j+1]
    return mxlen
 
while True:
    try:
        s1 = input()
        s2 = input()
        print(solution(s1,s2))
    except:
        break;


# 我的代码
try:
    s1 = input()
    s2 = input()
    ls, ss = (s1,s2) if len(s1)>len(s2) else (s2,s1)
    subs = {}
    max_sub = 0
    p1=p2=0
    for p1 in range(len(ss)):
        for p2 in range(p1+1, len(ss)+1):
            if ss[p1:p2] not in subs:
                subs[ss[p1:p2]] = len(ss[p1:p2])
                max_sub = max(max_sub, len(ss[p1:p2]))
    max_com_sub = 0
    for sub in subs:
        if sub in ls:
            max_com_sub = max(max_com_sub, subs[sub])
            if max_com_sub == max_sub:
                break
    print(max_com_sub)

except Exception as e:
    print(e.with_traceback)