Buggy python submission (verdict: Time Limit Exceeded):
def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    def match(c1, c2):
        if c1 == c2:
            return 1
        else:
            return 0

    if len(s1) == 0 or len(s2) == 0:
        return 0

    primary = [0] * len(s1)
    secondary = [0] * len(s1)

    for i in range(len(s2)):
        for j in range(len(s1)):
            if j == 0:
                secondary[j] = max(primary[j], match(s1[j], s2[i]))
            else:
                secondary[j] = max(secondary[j-1], primary[j],
                                   primary[j-1] + match(s1[j], s2[i]))

        primary, secondary = secondary, primary

    return primary[len(s1)-1]


def run():
    n = int(input())

    for _ in range(n):
        s1 = input()
        s2 = input()
        print(len_lcs(s1, s2))


if __name__ == '__main__':
    run()



Fixed submission:
import sys


def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    results = [0] * len(s1)

    for i, c2 in enumerate(s2):
        sec1, pr1 = 0, 0
        for j, c1 in enumerate(s1):
            pr2 = results[j]
            if c1 == c2:
                mval = pr1 + 1
            elif sec1 > pr2:
                mval = sec1
            else:
                mval = pr2

            results[j] = mval
            sec1, pr1 = mval, pr2

    return results[-1]


def run():
    n = int(input())
    s = []
    for line in sys.stdin:
        s.append(line.strip())
    for i in range(0, 2*n, 2):
        print(len_lcs(s[i], s[i+1]))

run()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    len1 = len(s1)
    len2 = len(s2)
    if len1 == 0 or len2 == 0:
        return 0

    primary = [0] * len1
    secondary = [0] * len1

    for i in range(len2):
        for j in range(len1):
            if s1[j] == s2[i]:
                match = 1
            else:
                match = 0
            if j == 0:
                secondary[j] = max(primary[j], match)
            else:
                secondary[j] = max(secondary[j-1], primary[j],
                                   primary[j-1] + match)

        primary, secondary = secondary, primary

    return primary[len1-1]


def run():
    i = 2 * int(input())
    s = ['', '']
    for line in sys.stdin:
        s[i % 2] = line.strip()
        if i % 2 == 1:
            print(len_lcs(*s))
        i -= 1


if __name__ == '__main__':
    run()



Fixed submission:
import sys


def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    results = [0] * len(s1)

    for i, c2 in enumerate(s2):
        sec1, pr1 = 0, 0
        for j, c1 in enumerate(s1):
            pr2 = results[j]
            if c1 == c2:
                mval = pr1 + 1
            elif sec1 > pr2:
                mval = sec1
            else:
                mval = pr2

            results[j] = mval
            sec1, pr1 = mval, pr2

    return results[-1]


def run():
    n = int(input())
    s = []
    for line in sys.stdin:
        s.append(line.strip())
    for i in range(0, 2*n, 2):
        print(len_lcs(s[i], s[i+1]))

run()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    len1 = len(s1)
    len2 = len(s2)
    if len1 == 0 or len2 == 0:
        return 0

    primary = [0] * len1
    secondary = [0] * len1

    for i in range(len2):
        for j in range(len1):
            if s1[j] == s2[i]:
                match = 1
            else:
                match = 0
            if j == 0:
                secondary[j] = max(primary[j], match)
            else:
                sc1, p1, p2 = secondary[j-1], primary[j-1] + match, primary[j]
                if sc1 > p1:
                    if p1 > p2:
                        secondary[j] = sc1
                    elif p2 > sc1:
                        secondary[j] = p2
                    else:
                        secondary[j] = sc1
                else:
                    if sc1 > p2:
                        secondary[j] = p1
                    elif p1 > p2:
                        secondary[j] = p1
                    else:
                        secondary[j] = p2
                # secondary[j] = max(secondary[j-1], primary[j],
                #                    primary[j-1] + match)

        primary, secondary = secondary, primary

    return primary[len1-1]


def run():
    input()
    s = []
    for line in sys.stdin:
        s.append(line.strip())
    for i in range(0, len(s), 2):
        print(len_lcs(s[i], s[i+1]))


if __name__ == '__main__':
    run()



Fixed submission:
import sys


def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    results = [0] * len(s1)

    for i, c2 in enumerate(s2):
        sec1, pr1 = 0, 0
        for j, c1 in enumerate(s1):
            pr2 = results[j]
            if c1 == c2:
                mval = pr1 + 1
            elif sec1 > pr2:
                mval = sec1
            else:
                mval = pr2

            results[j] = mval
            sec1, pr1 = mval, pr2

    return results[-1]


def run():
    n = int(input())
    s = []
    for line in sys.stdin:
        s.append(line.strip())
    for i in range(0, 2*n, 2):
        print(len_lcs(s[i], s[i+1]))

run()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    len1 = len(s1)
    len2 = len(s2)
    if len1 == 0 or len2 == 0:
        return 0

    primary = [0] * len1
    secondary = [0] * len1

    for i in range(len2):
        for j in range(len1):
            if s1[j] == s2[i]:
                match = 1
            else:
                match = 0
            if j == 0:
                if primary[j] > match:
                    secondary[j] = primary[j]
                else:
                    secondary[j] = match
            else:
                sc1, p1, p2 = secondary[j-1], primary[j-1] + match, primary[j]
                if sc1 > p1:
                    if p1 > p2:
                        secondary[j] = sc1
                    elif p2 > sc1:
                        secondary[j] = p2
                    else:
                        secondary[j] = sc1
                else:
                    if sc1 > p2:
                        secondary[j] = p1
                    elif p1 > p2:
                        secondary[j] = p1
                    else:
                        secondary[j] = p2
                # secondary[j] = max(secondary[j-1], primary[j],
                #                    primary[j-1] + match)

        primary, secondary = secondary, primary

    return primary[len1-1]


def run():
    input()
    s = []
    for line in sys.stdin:
        s.append(line.strip())
    for i in range(0, len(s), 2):
        print(len_lcs(s[i], s[i+1]))


if __name__ == '__main__':
    run()



Fixed submission:
import sys


def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    results = [0] * len(s1)

    for i, c2 in enumerate(s2):
        sec1, pr1 = 0, 0
        for j, c1 in enumerate(s1):
            pr2 = results[j]
            if c1 == c2:
                mval = pr1 + 1
            elif sec1 > pr2:
                mval = sec1
            else:
                mval = pr2

            results[j] = mval
            sec1, pr1 = mval, pr2

    return results[-1]


def run():
    n = int(input())
    s = []
    for line in sys.stdin:
        s.append(line.strip())
    for i in range(0, 2*n, 2):
        print(len_lcs(s[i], s[i+1]))

run()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


n = int(input())

primary = [0] * 1000
secondary = [0] * 1000


for i in range(n):
    s1 = sys.stdin.readline().strip()
    s2 = sys.stdin.readline().strip()

    len1 = len(s1)
    len2 = len(s2)

    for i in range(len1):
        primary[i] = 0
        secondary[i] = 0

    for i in range(len2):
        for j in range(len1):
            if s1[j] == s2[i]:
                matched = 1
            else:
                matched = 0

            if j == 0:
                secondary[j] = matched
            else:
                sc0 = secondary[j-1]
                pr0 = primary[j-1] + matched
                pr1 = primary[j]
                if sc0 > pr0:
                    if pr0 > pr1:
                        secondary[j] = sc0
                    elif sc0 > pr1:
                        secondary[j] = sc0
                    else:
                        secondary[j] = pr1
                else:
                    if sc0 > pr1:
                        secondary[j] = pr0
                    elif pr0 > pr1:
                        secondary[j] = pr0
                    else:
                        secondary[j] = pr1

        primary, secondary = secondary, primary

    print(primary[len1-1])



Fixed submission:
import sys


def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    results = [0] * len(s1)

    for i, c2 in enumerate(s2):
        sec1, pr1 = 0, 0
        for j, c1 in enumerate(s1):
            pr2 = results[j]
            if c1 == c2:
                mval = pr1 + 1
            elif sec1 > pr2:
                mval = sec1
            else:
                mval = pr2

            results[j] = mval
            sec1, pr1 = mval, pr2

    return results[-1]


def run():
    n = int(input())
    s = []
    for line in sys.stdin:
        s.append(line.strip())
    for i in range(0, 2*n, 2):
        print(len_lcs(s[i], s[i+1]))

run()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    results = [0] * len(s1)

    for i, c2 in enumerate(s2):
        sec1, pr1 = 0, 0
        for j, c1 in enumerate(s1):
            if c1 == c2:
                match = 1
            else:
                match = 0
            pr2 = results[j]
            mval = max(sec1, pr2, pr1 + match)
            results[j] = mval
            sec1, pr1 = mval, pr2

    return results[-1]


def run():
    n = int(input())
    s = []
    for line in sys.stdin:
        s.append(line.strip())
    for i in range(0, 2*n, 2):
        print(len_lcs(s[i], s[i+1]))


run()


Fixed submission:
import sys


def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    results = [0] * len(s1)

    for i, c2 in enumerate(s2):
        sec1, pr1 = 0, 0
        for j, c1 in enumerate(s1):
            pr2 = results[j]
            if c1 == c2:
                mval = pr1 + 1
            elif sec1 > pr2:
                mval = sec1
            else:
                mval = pr2

            results[j] = mval
            sec1, pr1 = mval, pr2

    return results[-1]


def run():
    n = int(input())
    s = []
    for line in sys.stdin:
        s.append(line.strip())
    for i in range(0, 2*n, 2):
        print(len_lcs(s[i], s[i+1]))

run()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    results = [0] * len(s1)

    for i, c2 in enumerate(s2):
        sec1, pr1 = 0, 0
        for j, c1 in enumerate(s1):
            if c1 == c2:
                match = 1
            else:
                match = 0
            pr2 = results[j]
            mval = max(sec1, pr2, pr1 + match)
            results[j] = mval
            sec1, pr1 = mval, pr2

    return results[-1]



n = int(input())
s = []
for line in sys.stdin:
    s.append(line.strip())
for i in range(0, 2*n, 2):
    print(len_lcs(s[i], s[i+1]))





Fixed submission:
import sys


def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    results = [0] * len(s1)

    for i, c2 in enumerate(s2):
        sec1, pr1 = 0, 0
        for j, c1 in enumerate(s1):
            pr2 = results[j]
            if c1 == c2:
                mval = pr1 + 1
            elif sec1 > pr2:
                mval = sec1
            else:
                mval = pr2

            results[j] = mval
            sec1, pr1 = mval, pr2

    return results[-1]


def run():
    n = int(input())
    s = []
    for line in sys.stdin:
        s.append(line.strip())
    for i in range(0, 2*n, 2):
        print(len_lcs(s[i], s[i+1]))

run()