Submission #1176105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176105		chromatic	Necklace (Subtask 4) (BOI19_necklace4)	Pypy 3	0 / 15	777 ms	65428 KiB

necklace

def booth(s):
    """
    Compute the lexicographically minimal rotation of s using Booth's algorithm.
    """
    n = len(s)
    s2 = s + s
    i, j, k = 0, 1, 0
    while i < n and j < n and k < n:
        if s2[i+k] == s2[j+k]:
            k += 1
        else:
            if s2[i+k] > s2[j+k]:
                i = i + k + 1
                if i == j:
                    i += 1
            else:
                j = j + k + 1
                if i == j:
                    j += 1
            k = 0
    pos = min(i, j)
    return s2[pos:pos+n]

def canonical(s):
    """
    Returns the canonical representation of the necklace corresponding to s,
    which is the lexicographically smaller of the minimal rotation of s and
    the minimal rotation of its reverse.
    """
    rot1 = booth(s)
    rot2 = booth(s[::-1])
    return min(rot1, rot2)

def exists_common_necklace(L, s1, s2):
    """
    For a fixed length L, checks if there is a substring in s1 and a substring in s2
    that yield the same canonical necklace.
    Returns a tuple (i, j) of starting indices if found, or None otherwise.
    """
    canon_map = {}
    for i in range(len(s1) - L + 1):
        sub = s1[i:i+L]
        canon = canonical(sub)
        # store the first occurrence for this canonical form
        if canon not in canon_map:
            canon_map[canon] = i

    for j in range(len(s2) - L + 1):
        sub = s2[j:j+L]
        canon = canonical(sub)
        if canon in canon_map:
            return canon_map[canon], j
    return None

def main():
    import sys
    # Read the two strings (removing any trailing newline)
    s1 = sys.stdin.readline().strip()
    s2 = sys.stdin.readline().strip()
    
    n1, n2 = len(s1), len(s2)
    max_possible = min(n1, n2)
    
    # Binary search for the maximum L for which there is a common necklace
    low, high = 1, max_possible
    best = None
    best_L = 0
    while low <= high:
        mid = (low + high) // 2
        res = exists_common_necklace(mid, s1, s2)
        if res is not None:
            best = res
            best_L = mid
            low = mid + 1  # try to find a longer common necklace
        else:
            high = mid - 1  # try shorter lengths

    # Output the result.
    # First line: the maximum length.
    # Second line: starting positions in s1 and s2.
    if best is not None:
        print(best_L)
        print(best[0], best[1])
    else:
        # According to the problem, a positive answer always exists.
        print("0")
        print("0 0")

if __name__ == '__main__':
    main()

Compilation message (stdout)

Compiling 'necklace.py'...

=======
  adding: __main__.pyc (deflated 43%)

=======

• Subtask 1: 0 / 15