Problem:


Problem G: Repeated Subsequences

You are a treasure hunter traveling around the world. Finally, you’ve got an ancient text
indicating the place where the treasure was hidden. The ancient text looks like a meaningless
string of characters at first glance. Actually, the secret place is embedded as the longest repeated
subsequence of the text.

Well, then, what is the longest repeated subsequence of a string? First, you split the given string
S into two parts F and R. Then, you take the longest common subsequence L of F and R
(longest string L that is a subsequence of both F and R). Since there are many possible ways
to split S into two parts, there are many possible L's. The longest repeated subsequence is the
longest one among them. For example, the longest repeated subsequence of “ABCABCABAB”
is “ABAB”, which is obtained when you split “ABCABCABAB” into “ABCABC” and “ABAB”.

Now your task is clear. Please find the longest repeated subsequence and get the hidden treasure!

Input

The input consists of multiple data sets. Each data set comes with a single line that contains
one string of up to 300 capital letters. It is guaranteed that there is at least one repeated
subsequence in each string.

The end of input is indicated by a line that contains “#END”. This line should not be processed.

Output

For each data set, print the longest repeated subsequence on a line. If there are multiple longest
subsequence, print any one of them.

Sample Input

ABCABCABAB
ZZZZZZZZZZZZ
#END

Output for the Sample Input

ABAB
ZZZZZZ



Sample input:
ABCABCABAB
ZZZZZZZZZZZZ
#END


Sample output:
ABAB
ZZZZZZ

Submission status: Wrong Answer

Solution code:
def lcs(x, y):
    rec = []
    idx = []
    for c in y:
        s = 0
        for i, k in enumerate(idx):
            t = x.find(c, s) + 1
            if t < 1:
                break
            if t < k:
                idx[i] = t
            s = k
        else:
            t = x.find(c, s) + 1
            if t:
                idx.append(t)
        rec.append(idx.copy())
    
    if idx:
        lcs = ''
        pos = len(idx) - 1
        for line, yc in zip(rec[::-1], y[::-1]):
            i = line[pos] - 1
            xc = x[i]
            if xc == yc:
                lcs += xc
                if pos == 0:
                    return lcs[::-1]
                pos -= 1
    else:
        return ''

def solve():
    import sys
    file_input = sys.stdin
    ans_out = []
    for s in file_input:
        s = s.rstrip()
        if s == '#END':
            break
        sep = len(s) // 2
        ans = lcs(s[:sep], s[sep:])
        ans_len = len(ans)
        print(ans)

solve()

Submission status: Wrong Answer

Solution code:
def lcs(x, y, pre_lcs, pre_lcs_len):
    rec = []
    idx = []
    for c in y:
        s = 0
        for i, k in enumerate(idx):
            t = x.find(c, s) + 1
            if t < 1:
                break
            if t < k:
                idx[i] = t
            s = k
        else:
            t = x.find(c, s) + 1
            if t:
                idx.append(t)
        rec.append(idx.copy())
    
    lcs_len = len(idx)
    if lcs_len > pre_lcs_len:
        lcs = ''
        pos = len(idx) - 1
        for line, yc in zip(rec[::-1], y[::-1]):
            i = line[pos] - 1
            xc = x[i]
            if xc == yc:
                lcs += xc
                if pos == 0:
                    return (lcs[::-1], lcs_len)
                pos -= 1
    else:
        return (pre_lcs, pre_lcs_len)

def lrs(s):
    s = s.rstrip()
    s_len = len(s)
    sep = s_len // 2
    ans, ans_len = lcs(s[:sep], s[sep:], '', 0)
    while sep > ans_len:
        ans, ans_len = lcs(s[:-sep], s[-sep:], ans, ans_len)
        sep -= 1
        ans, ans_len = lcs(s[:sep], s[sep:], ans, ans_len)
    return ans

import sys

input_lines = sys.stdin.readlines()

for line in input_lines[:-1]:
    print(1)

Submission status: Accepted

Solution code:
def lcs(x, y, pre_lcs, pre_lcs_len):
    pm = dict((zip('ABCDEFGHIJKLMNOPQRSTUVWXYZ', [0] * 26)))
    for c in pm:
        for i, xc in enumerate(x):
            if c == xc:
                pm[c] |= (1 << i)
    
    V = (1 << len(x)) - 1
    rec = []
    
    for yc in y:
        V = ((V + (V & pm[yc])) | (V & ~pm[yc]))
        rec.append(bin(V)[-len(x):])
    
    lcs_len = bin(V)[-len(x):].count('0')
    
    if lcs_len > pre_lcs_len:
        rx = x[::-1]
        lcs = ''
        idx = 0
        for v, yc in zip(rec[::-1], reversed(y)):
            idx = v.find('0', idx)
            if yc == rx[idx]:
                lcs += yc
                if len(lcs) == lcs_len:
                    return (lcs[::-1], lcs_len)
                idx += 1
    else:
        return (pre_lcs, pre_lcs_len)

from sys import stdin

def solve():
    file_input = stdin
    ans_out = []
    for s in file_input:
        s = s.rstrip()
        if s[0] == '#':
            break
        s_len = len(s)
        sep = s_len // 2
        ans, ans_len = lcs(s[:sep], s[sep:], '', 0)
        while sep > ans_len:
            ans, ans_len = lcs(s[:-sep], s[-sep:], ans, ans_len)
            sep -= 1
            ans, ans_len = lcs(s[:sep], s[sep:], ans, ans_len)
        ans_out.append(ans)
    print(*ans_out, sep='\n')

solve()

Submission status: Runtime Error

Solution code:
def lcs(x, y):
    rec = []
    idx = []
    for c in y:
        s = 0
        for i, k in enumerate(idx):
            t = x.find(c, s) + 1
            if t < 1:
                break
            if t < k:
                idx[i] = t
            s = k
        else:
            t = x.find(c, s) + 1
            if t:
                idx.append(t)
        rec.append(idx.copy())
    
    lcs = ''
    pos = len(idx) - 1
    for line, yc in zip(rec[::-1], y[::-1]):
        i = line[pos] - 1
        xc = x[i]
        if xc == yc:
            lcs += xc
            if pos == 0:
                return lcs[::-1]
            pos -= 1

def solve():
    import sys
    file_input = sys.stdin
    for s in file_input:
        s = s.rstrip()
        if s == '#END':
            break
        sep = len(s) // 2
        ans = lcs(s[:sep], s[sep:])
        ans_len = len(ans)
        while sep > len(ans):
            sep -= 1
            a1 = lcs(s[:sep], s[sep:])
            a2 = lcs(s[:-sep], s[-sep:])
            if ans_len < len(a1):
                ans = a1
                ans_len = len(ans)
            if ans_len < len(a2):
                ans = a2
                ans_len = len(ans)
        print(ans)

solve()

Submission status: Runtime Error

Solution code:
def lcs(x, y):
    rec = []
    idx = []
    for c in y:
        s = 0
        for i, k in enumerate(idx):
            t = x.find(c, s) + 1
            if t < 1:
                break
            if t < k:
                idx[i] = t
            s = k
        else:
            t = x.find(c, s) + 1
            if t:
                idx.append(t)
        rec.append(idx.copy())
    
    if idx:
        lcs = ''
        pos = len(idx) - 1
        for line, yc in zip(rec[::-1], y[::-1]):
            i = line[pos] - 1
            xc = x[i]
            if xc == yc:
                lcs += xc
                if pos == 0:
                    return lcs[::-1]
                pos -= 1
    else:
        return ''

def solve():
    import sys
    file_input = sys.stdin
    ans_out = []
    for s in file_input:
        s = s.rstrip()
        if s == '#END':
            break
        sep = len(s) // 2
        ans = lcs(s[:sep], s[sep:])
        ans_len = len(ans)
        while sep > len(ans):
            a1 = lcs(s[:-sep], s[-sep:])
            sep -= 1
            a2 = lcs(s[:sep], s[sep:])
            if ans_len < len(a1):
                ans = a1
                ans_len = len(ans)
            if ans_len < len(a2):
                ans = a2
                ans_len = len(ans)
        ans_out.append(ans)
    print(*ans_out, sep='\n')

solve()

Submission status: Runtime Error

Solution code:
def lcs(x, y):
    rec = []
    idx = []
    for c in y:
        s = 0
        for i, k in enumerate(idx):
            t = x.find(c, s) + 1
            if t < 1:
                break
            if t < k:
                idx[i] = t
            s = k
        else:
            t = x.find(c, s) + 1
            if t:
                idx.append(t)
        rec.append(idx.copy())
    
    if idx:
        lcs = ''
        pos = len(idx) - 1
        for line, yc in zip(rec[::-1], y[::-1]):
            i = line[pos] - 1
            xc = x[i]
            if xc == yc:
                lcs += xc
                if pos == 0:
                    return lcs[::-1]
                pos -= 1
    else:
        return ''

def solve():
    import sys
    file_input = sys.stdin
    ans_out = []
    for s in file_input:
        s = s.rstrip()
        if s == '#END':
            break
        sep = len(s) // 2
        ans = lcs(s[:sep], s[sep:])
        ans_len = len(ans)
        while sep > len(ans):
            a1 = lcs(s[:-sep], s[-sep:])
            sep -= 1
            a2 = lcs(s[:sep], s[sep:])
            if ans_len < len(a1):
                ans = a1
                ans_len = len(ans)
            if ans_len < len(a2):
                ans = a2
                ans_len = len(ans)
        print(ans)

solve()

Submission status: Runtime Error

Solution code:
def lcs(x, y, pre_lcs, pre_lcs_len):
    rec = []
    idx = []
    for c in y:
        s = 0
        for i, k in enumerate(idx):
            t = x.find(c, s) + 1
            if t < 1:
                break
            if t < k:
                idx[i] = t
            s = k
        else:
            t = x.find(c, s) + 1
            if t:
                idx.append(t)
        rec.append(idx.copy())
    
    lcs_len = len(idx)
    if lcs_len > pre_lcs_len:
        lcs = ''
        pos = len(idx) - 1
        for line, yc in zip(rec[::-1], y[::-1]):
            i = line[pos] - 1
            xc = x[i]
            if xc == yc:
                lcs += xc
                if pos == 0:
                    return (lcs[::-1], lcs_len)
                pos -= 1
    else:
        return (pre_lcs, pre_lcs_len)

def solve():
    import sys
    file_input = sys.stdin
    ans_out = []
    for s in file_input:
        s = s.rstrip()
        if s == '#END':
            break
        s_len = len(s)
        sep = s_len // 2
        ans, ans_len = lcs(s[:sep], s[sep:], '', 0)
        sep = s_len - ans_len - 1
        while sep > ans_len:
            ans, ans_len = lcs(s[:sep], s[sep:], ans, ans_len)
            sep -= 1
        ans_out.append(ans)
    print(*ans_out, sep='\n')

solve()

Submission status: Runtime Error

Solution code:
def lcs(x, y, pre_lcs, pre_lcs_len):
    rec = []
    idx = []
    for c in y:
        s = 0
        for i, k in enumerate(idx):
            t = x.find(c, s) + 1
            if t < 1:
                break
            if t < k:
                idx[i] = t
            s = k
        else:
            t = x.find(c, s) + 1
            if t:
                idx.append(t)
        rec.append(idx.copy())
    
    lcs_len = len(idx)
    if lcs_len > pre_lcs_len:
        lcs = ''
        pos = len(idx) - 1
        for line, yc in zip(rec[::-1], y[::-1]):
            i = line[pos] - 1
            xc = x[i]
            if xc == yc:
                lcs += xc
                if pos == 0:
                    return (lcs[::-1], lcs_len)
                pos -= 1
    else:
        return (pre_lcs, pre_lcs_len)

def solve():
    import sys
    #file_input = sys.stdin
    file_input = open('2090_in', 'r')#
    ans_out = []
    for s in file_input:
        s = s.rstrip()
        if s == '#END':
            break
        s_len = len(s)
        sep = s_len // 2
        ans, ans_len = lcs(s[:sep], s[sep:], '', 0)
        while sep > ans_len:
            ans, ans_len = lcs(s[:-sep], s[-sep:], ans, ans_len)
            sep -= 1
            ans, ans_len = lcs(s[:sep], s[sep:], ans, ans_len)
        print(ans)

solve()

Submission status: Runtime Error

Solution code:
def lcs(x, y, pre_lcs, pre_lcs_len):
    rec = []
    idx = []
    for c in y:
        s = 0
        for i, k in enumerate(idx):
            t = x.find(c, s) + 1
            if t < 1:
                break
            if t < k:
                idx[i] = t
            s = k
        else:
            t = x.find(c, s) + 1
            if t:
                idx.append(t)
        rec.append(idx.copy())
    
    lcs_len = len(idx)
    if lcs_len > pre_lcs_len:
        lcs = ''
        pos = len(idx) - 1
        for line, yc in zip(rec[::-1], y[::-1]):
            i = line[pos] - 1
            xc = x[i]
            if xc == yc:
                lcs += xc
                if pos == 0:
                    return (lcs[::-1], lcs_len)
                pos -= 1
    else:
        return (pre_lcs, pre_lcs_len)

def solve():
    import sys
    file_input = sys.stdin
    ans_out = []
    for s in file_input:
        s = s.rstrip()
        if s == '#END':
            break
        s_len = len(s)
        sep = s_len // 2
        ans, ans_len = lcs(s[:sep], s[sep:], '', 0)
        while sep > ans_len:
            ans, ans_len = lcs(s[:-sep], s[-sep:], ans, ans_len)
            sep -= 1
            ans, ans_len = lcs(s[:sep], s[sep:], ans, ans_len)
        print(ans)

solve()

Submission status: Runtime Error

Solution code:
def lcs(x, y, pre_lcs, pre_lcs_len):
    rec = []
    idx = []
    for c in y:
        s = 0
        for i, k in enumerate(idx):
            t = x.find(c, s) + 1
            if t < 1:
                break
            if t < k:
                idx[i] = t
            s = k
        else:
            t = x.find(c, s) + 1
            if t:
                idx.append(t)
        rec.append(idx.copy())
    
    lcs_len = len(idx)
    if lcs_len > pre_lcs_len:
        lcs = ''
        pos = len(idx) - 1
        for line, yc in zip(rec[::-1], y[::-1]):
            i = line[pos] - 1
            xc = x[i]
            if xc == yc:
                lcs += xc
                if pos == 0:
                    return (lcs[::-1], lcs_len)
                pos -= 1
    else:
        return (pre_lcs, pre_lcs_len)

def solve():
    import sys
    file_input = sys.stdin
    ans_out = []
    for s in file_input:
        s = s.rstrip()
        if s == '#END':
            break
        s_len = len(s)
        sep = s_len // 2
        ans, ans_len = lcs(s[:sep], s[sep:], '', 0)
        while sep > ans_len:
            ans, ans_len = lcs(s[:-sep], s[-sep:], ans, ans_len)
            sep -= 1
            ans, ans_len = lcs(s[:sep], s[sep:], ans, ans_len)
        ans_out.append(ans)
    print(*ans_out, sep='\n')

solve()

Submission status: Runtime Error

Solution code:
def lcs(x, y, pre_lcs, pre_lcs_len):
    rec = []
    idx = []
    for c in y:
        s = 0
        for i, k in enumerate(idx):
            t = x.find(c, s) + 1
            if t < 1:
                break
            if t < k:
                idx[i] = t
            s = k
        else:
            t = x.find(c, s) + 1
            if t:
                idx.append(t)
        rec.append(idx.copy())
    
    lcs_len = len(idx)
    if lcs_len > pre_lcs_len:
        lcs = ''
        pos = len(idx) - 1
        for line, yc in zip(rec[::-1], y[::-1]):
            i = line[pos] - 1
            xc = x[i]
            if xc == yc:
                lcs += xc
                if pos == 0:
                    return (lcs[::-1], lcs_len)
                pos -= 1
    else:
        return (pre_lcs, pre_lcs_len)

def lrs(s):
    s = s.rstrip()
    s_len = len(s)
    sep = s_len // 2
    ans, ans_len = lcs(s[:sep], s[sep:], '', 0)
    while sep > ans_len:
        ans, ans_len = lcs(s[:-sep], s[-sep:], ans, ans_len)
        sep -= 1
        ans, ans_len = lcs(s[:sep], s[sep:], ans, ans_len)
    return ans

import sys

input_lines = sys.stdin.readlines()

print('\n'.join(map(lrs, input_lines[:-1])))

Submission status: Runtime Error

Solution code:
def lcs(x, y, pre_lcs, pre_lcs_len):
    rec = []
    idx = []
    for c in y:
        s = 0
        for i, k in enumerate(idx):
            t = x.find(c, s) + 1
            if t < 1:
                break
            if t < k:
                idx[i] = t
            s = k
        else:
            t = x.find(c, s) + 1
            if t:
                idx.append(t)
        rec.append(idx.copy())
    
    lcs_len = len(idx)
    if lcs_len > pre_lcs_len:
        lcs = ''
        pos = len(idx) - 1
        for line, yc in zip(rec[::-1], y[::-1]):
            i = line[pos] - 1
            xc = x[i]
            if xc == yc:
                lcs += xc
                if pos == 0:
                    return (lcs[::-1], lcs_len)
                pos -= 1
    else:
        return (pre_lcs, pre_lcs_len)

def lrs(s):
    s = s.rstrip()
    s_len = len(s)
    sep = s_len // 2
    ans, ans_len = lcs(s[:sep], s[sep:], '', 0)
    while sep > ans_len:
        ans, ans_len = lcs(s[:-sep], s[-sep:], ans, ans_len)
        sep -= 1
        ans, ans_len = lcs(s[:sep], s[sep:], ans, ans_len)
    return ans

import sys

input_lines = sys.stdin.readlines()

for line in input_lines[:-1]:
    print(lrs(line))

Submission status: Runtime Error

Solution code:
def lcs(x, y, pre_lcs, pre_lcs_len):
    rec = []
    idx = []
    for c in y:
        s = 0
        for i, k in enumerate(idx):
            t = x.find(c, s) + 1
            if t < 1:
                break
            if t < k:
                idx[i] = t
            s = k
        else:
            t = x.find(c, s) + 1
            if t:
                idx.append(t)
        rec.append(idx.copy())
    
    lcs_len = len(idx)
    if lcs_len > pre_lcs_len:
        lcs = ''
        pos = len(idx) - 1
        for line, yc in zip(rec[::-1], y[::-1]):
            i = line[pos] - 1
            xc = x[i]
            if xc == yc:
                lcs += xc
                if pos == 0:
                    return (lcs[::-1], lcs_len)
                pos -= 1
    else:
        return (pre_lcs, pre_lcs_len)

def solve():
    import sys
    file_input = sys.stdin
    ans_out = []
    for s in file_input:
        s = s.rstrip()
        if s[0] == '#':
            break
        s_len = len(s)
        sep = s_len // 2
        ans, ans_len = lcs(s[:sep], s[sep:], '', 0)
        while sep > ans_len:
            ans, ans_len = lcs(s[:-sep], s[-sep:], ans, ans_len)
            sep -= 1
            ans, ans_len = lcs(s[:sep], s[sep:], ans, ans_len)
        ans_out.append(ans)
    print(*ans_out, sep='\n')

solve()

Submission status: Runtime Error

Solution code:
def lcs(x, y, pre_lcs, pre_lcs_len):
    rec = []
    idx = []
    for c in y:
        s = 0
        for i, k in enumerate(idx):
            t = x.find(c, s) + 1
            if t < 1:
                break
            if t < k:
                idx[i] = t
            s = k
        else:
            t = x.find(c, s) + 1
            if t:
                idx.append(t)
        rec.append(idx.copy())
    
    lcs_len = len(idx)
    if lcs_len > pre_lcs_len:
        lcs = ''
        pos = len(idx) - 1
        for line, yc in zip(rec[::-1], y[::-1]):
            i = line[pos] - 1
            xc = x[i]
            if xc == yc:
                lcs += xc
                if pos == 0:
                    return (lcs[::-1], lcs_len)
                pos -= 1
    else:
        return (pre_lcs, pre_lcs_len)

def solve():
    import sys
    file_input = sys.stdin
    for s in file_input:
        s = s.rstrip()
        if s[0] == '#':
            break
        s_len = len(s)
        sep = s_len // 2
        ans, ans_len = lcs(s[:sep], s[sep:], '', 0)
        while sep > ans_len:
            ans, ans_len = lcs(s[:-sep], s[-sep:], ans, ans_len)
            sep -= 1
            ans, ans_len = lcs(s[:sep], s[sep:], ans, ans_len)
        print(ans)

solve()