Submission #790209

#	Time	Username	Problem	Language	Result	Execution time	Memory
790209		beaconmc	Necklace (Subtask 1-3) (BOI19_necklace1)	Pypy 3	17 / 85	443 ms	161196 KiB

necklace

a = input()
b = input()

maxi = 0
ans = []
for qq in range(2):
    dp = [[0 for i in range(len(b)+1)]for j in range(len(a)+1)]

    for i in range(1, len(a)+1):
        for j in range(1, len(b)+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = 0

    if maxi < max([max(i) for i in dp]):
        maxi = max([max(i) for i in dp])
        ans = 0
        for i in range(1, len(a)+1):
            for j in range(1, len(b)+1):
                if dp[i][j] == maxi:
                    if qq == 1:
                        ans = [i-maxi,len(b)-j]
                    else:
                        ans = [i-maxi,j-maxi]
    b = b[::-1]
print(maxi)
print(ans[0], ans[1])
    

• Subtask 1: 5 / 25
• Subtask 2: 4 / 20
• Subtask 3: 8 / 40