9251

편집 시간: 2022년 2월 18일 오후 6:45

잘못된 풀이

first = input()
second = input()

cache = [(0, 9999) for _ in range(len(first))]

def find_indexes_in_second(char):
    result = []
    for i in range(len(second)):
        if second[i] == char:
            result.append(i)
    return result

for i in range(len(first)):
    char = first[i]
    indexes = find_indexes_in_second(char)
    if len(indexes) == 0:
        continue
    cache[i] = (1, indexes[0])
    for j in range(i):
        max_length = cache[j][0]
        last_index = cache[j][1]
        for index in indexes:
            if last_index < index:
                if cache[i][0] < max_length + 1:
                    cache[i] = (max_length + 1, index)
                    break
                elif cache[i][0] == max_length + 1 and index < cache[i][1]:
                    cache[i] = (max_length + 1, index)
                    break

print(max(cache)[0])