Submission #1176099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176099		chromatic	Necklace (Subtask 4) (BOI19_necklace4)	Pypy 3	Compilation error	0 ms	0 KiB

necklace

function canonical(s):
    r = reverse(s)
    min_rotation1 = find_min_rotation(s)  // using Booth's algorithm
    min_rotation2 = find_min_rotation(r)
    return the lexicographically smaller string of (min_rotation1, min_rotation2)

function existsCommonNecklace(L):
    mapJill = {}   // mapping canonical representation -> starting position
    for i from 0 to (length(Jill's string) - L):
        subJill = Jill's string from i to i+L-1
        canonJill = canonical(subJill)
        mapJill[canonJill] = i

    for j from 0 to (length(Jane's string) - L):
        subJane = Jane's string from j to j+L-1
        canonJane = canonical(subJane)
        if canonJane exists in mapJill:
            return (mapJill[canonJane], j)  // valid starting positions
    return None

// Binary search for the maximum L
low = 1
high = min(length(Jill's string), length(Jane's string))
answer = (0, None, None)

while low <= high:
    mid = (low + high) // 2
    result = existsCommonNecklace(mid)
    if result is not None:
        answer = (mid, result.first, result.second)
        low = mid + 1   // try to find a longer necklace
    else:
        high = mid - 1  // try shorter lengths

// Output the answer
print(answer.length)
print(answer.jillStart, answer.janeStart)

Compilation message (stdout)

Compiling 'necklace.py'...
***   File "necklace.py", line 3
    min_rotation1 = find_min_rotation(s)  // using Booth's algorithm
                                                        ^
SyntaxError: end of line (EOL) while scanning string literal


=======