common_substring

class Solution:
    """
    @param A: A string
    @param B: A string
    @return: the length of the longest common substring.
    """

    def longestCommonSubstring(self, A, B):
        k = 0
        maxlenT = 0
        markA = True
        if len(A) > len(B):
            lt = len(B)
            markA = False
        else:
            lt = len(A)
            markA = True

        while k < lt:
            if not markA:
                if B[k] in A:
                    challenge = self.dothe(A, B[k:])
                    if maxlenT < challenge:
                        maxlenT = challenge
                    k += 1
                else:
                    k += 1
            else:
                if A[k] in B:
                    challenge = self.dothe(B, A[k:])
                    if maxlenT < challenge:
                        maxlenT = challenge

                    k += 1
                else:
                    k += 1
        return maxlenT

    def dothe(self, Ad, Bd):
        # Write your code here
        maxlen = 0
        if len(Bd) == 0:
            return 0
        lps_target = self.preprocess(Bd)
        index_source = 0
        index_target = 0
        while True:
            if index_target == len(Bd):
                return maxlen
            if index_source == len(Ad):
                return maxlen
            if Bd[index_target] == Ad[index_source]:
                if index_target + 1 > maxlen:
                    maxlen = index_target + 1
                index_source += 1
                index_target += 1
            else:
                if index_target != 0:
                    index_target = lps_target[index_target - 1]
                else:
                    index_source += 1

    def preprocess(self, target):
        if len(target) == 1:
            return [0]
        i = 1  # this tracks the index of substring we are going to discover
        length = 0  # this tracks the length of lps
        lps = [0] * len(target)
        while i < len(target):
            if target[length] == target[i]:
                lps[i] = length + 1
                length += 1
                i += 1
            else:
                if length == 0:
                    lps[i] = 0
                    i += 1
                else:
                    length = lps[length - 1]
        return lps