#!/usr/bin/env python
# coding:utf-8

"""
最长公共子序列（longest common sequence）
最长公共子串（longest common substring）

区别：
    子序列：不需要连续
    子串：需要连续
"""
# ================================================================================
"""
[编程题] 最长公共子序列
时间限制：3秒
空间限制：32768K
对于两个字符串，请设计一个高效算法，求他们的最长公共子序列的长度，
这里的最长公共子序列定义为有两个序列U1,U2,U3...Un和V1,V2,V3...Vn,其中Ui&ltUi+1，Vi&ltVi+1。且A[Ui] == B[Vi]。
给定两个字符串A和B，同时给定两个串的长度n和m，请返回最长公共子序列的长度。保证两串长度均小于等于300。
测试样例：
"1A2C3D4B56",10,"B1D23CA45B6A",12
返回：6
"""

"""
[编程题] 最长公共子串
时间限制：3秒
空间限制：32768K
对于两个字符串，请设计一个时间复杂度为O(m*n)的算法(这里的m和n为两串的长度)，求出两串的最长公共子串的长度。
这里的最长公共子串的定义为两个序列U1,U2,..Un和V1,V2,...Vn，其中Ui + 1 == Ui+1,Vi + 1 == Vi+1，同时Ui == Vi。
给定两个字符串A和B，同时给定两串的长度n和m。
测试样例：
"1AB2345CD",9,"12345EF",7
返回：4
"""
# ================================================================================
"""
动态规划求解:


    最长公共子序列（longest common sequence）
        状态转义公式：
                    # ------------------------------
                    if A[j-1] == B[i-1]:
                        dp[i][j] = dp[i-1][j-1] + 1
                    else:
                        dp[i][j] = max(
                            dp[i-1][j],
                            dp[i][j-1]
                        )
                        pass
                    # ------------------------------
        最终结果：dp 矩阵的最右下角元素
        
        
    最长公共子串（longest common substring）
        状态转义公式：
                    # ------------------------------
                    if A[j-1] == B[i-1]:
                        dp[i][j] = dp[i-1][j-1] + 1
                    else:
                        dp[i][j] = 0
                        pass
                    # ------------------------------
        最终结果：dp 矩阵中的最大值
"""
# ================================================================================


class LCS:
    def findLCS(self, A, n, B, m):
        n = len(A)
        m = len(B)
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
        for i in range(m+1):
            for j in range(n+1):
                if i and j:
                    # ------------------------------
                    if A[j-1] == B[i-1]:
                        dp[i][j] = dp[i-1][j-1] + 1
                    else:
                        dp[i][j] = max(
                            dp[i-1][j],
                            dp[i][j-1]
                        )
                        pass
                    # ------------------------------
                    pass
                pass
            pass
        #
        for x in dp:
            print x
            pass
        #
        return dp[-1][-1]  # ------------------------------


# ================================================================================


class LongestSubstring:
    def findLongest(self, A, n, B, m):
        n = len(A)
        m = len(B)
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
        for i in range(m+1):
            for j in range(n+1):
                if i and j:
                    # ------------------------------
                    if A[j-1] == B[i-1]:
                        dp[i][j] = dp[i-1][j-1] + 1
                    else:
                        dp[i][j] = 0
                        pass
                    # ------------------------------
                    pass
                pass
            pass
        #
        for x in dp:
            print x
            pass
        #
        return max([max(line) for line in dp])  # ------------------------------


# ================================================================================
# ================================================================================
# ================================================================================
# ================================================================================

lcs = LCS()
print lcs.findLCS(
    '123abc', 0,
    '1a2b3c', 0
)
# 4

ls = LongestSubstring()
print ls.findLongest(
    "1AB2345CD", 9,
    "12345EF", 7
)
# 4
