Test (Codeforces 25E)
Tags: Others, hashing

Sometimes it is hard to prepare tests for programming problems. Now Bob is preparing tests to new problem about strings — input data to his problem is one string. Bob has 3 wrong solutions to this problem. The first gives the wrong answer if the input data contains the substring s1, the second enters an infinite loop if the input data contains the substring s2, and the third requires too much memory if the input data contains the substring s3. Bob wants these solutions to fail single test. What is the minimal length of test, which couldn't be passed by all three Bob's solutions?

Input: There are exactly 3 lines in the input data. The i-th line contains string si. All the strings are non-empty, consists of lowercase Latin letters, the length of each string doesn't exceed 105.

Output: Output one number — what is minimal length of the string, containing s1, s2 and s3 as substrings.


Sample Inputs:
ab
bc
cd

abacaba
abaaba
x

Sample Outputs:
4

11

Solution (Python):
import sys, math
input = sys.stdin.readline

def listStr():
    return list(input().strip())
from itertools import permutations as pp

def solve():
    S = [listStr(), listStr(), listStr()]
    overlap = [[0 for j in range(3)] for i in range(3)]

    def calc(x, y):
        (s1, s2) = (S[x], S[y])
        if not s1:
            return [0]
        if not s2:
            return [0]
        N = len(s1)
        T = [0] * N
        pos = 1
        cnd = 0
        while pos < N:
            if s1[pos] == s1[cnd]:
                cnd += 1
                T[pos] = cnd
            else:
                while cnd:
                    cnd = T[cnd - 1]
                    if s1[pos] == s1[cnd]:
                        cnd += 1
                        T[pos] = cnd
                        break
            pos += 1
        pos = 0
        cnd = 0
        N2 = len(s2)
        T2 = [0] * N2
        while pos < N2:
            if s2[pos] == s1[cnd]:
                cnd += 1
                T2[pos] = cnd
            else:
                while cnd:
                    cnd = T[cnd - 1]
                    if s2[pos] == s1[cnd]:
                        cnd += 1
                        T2[pos] = cnd
                        break
            if cnd == N:
                cnd = T[cnd - 1]
            pos += 1
        return T2
    for ii in range(3):
        for jj in range(ii + 1, 3):
            X = calc(ii, jj)
            if max(X) == len(S[ii]):
                S[ii] = ''
                y = 0
            else:
                y = X[-1]
            overlap[ii][jj] = y
            X = calc(jj, ii)
            if max(X) == len(S[jj]):
                S[jj] = ''
                y = 0
            else:
                y = X[-1]
            overlap[jj][ii] = y
    ops = pp('012')
    ans = len(S[0]) + len(S[1]) + len(S[2])
    best = ans
    for op in ops:
        tmp = ans
        tmp -= overlap[int(op[0])][int(op[1])]
        tmp -= overlap[int(op[1])][int(op[2])]
        best = min(best, tmp)
    return best
print(solve())

Solution (Python):
def listStr():
    return list(input().strip())
from itertools import permutations as pp

def solve():
    S = [listStr(), listStr(), listStr()]
    overlap = [[0 for j in range(3)] for i in range(3)]

    def calc(x, y):
        (s1, s2) = (S[x], S[y])
        if not s1:
            return [0]
        if not s2:
            return [0]
        N = len(s1)
        T = [0] * N
        pos = 1
        cnd = 0
        while pos < N:
            if s1[pos] == s1[cnd]:
                cnd += 1
                T[pos] = cnd
            else:
                while cnd:
                    cnd = T[cnd - 1]
                    if s1[pos] == s1[cnd]:
                        cnd += 1
                        T[pos] = cnd
                        break
            pos += 1
        pos = 0
        cnd = 0
        N2 = len(s2)
        T2 = [0] * N2
        while pos < N2:
            if s2[pos] == s1[cnd]:
                cnd += 1
                T2[pos] = cnd
            else:
                while cnd:
                    cnd = T[cnd - 1]
                    if s2[pos] == s1[cnd]:
                        cnd += 1
                        T2[pos] = cnd
                        break
            if cnd == N:
                cnd = T[cnd - 1]
            pos += 1
        return T2
    for ii in range(3):
        for jj in range(ii + 1, 3):
            X = calc(ii, jj)
            if max(X) == len(S[ii]):
                S[ii] = ''
                y = 0
            else:
                y = X[-1]
            overlap[ii][jj] = y
            X = calc(jj, ii)
            if max(X) == len(S[jj]):
                S[jj] = ''
                y = 0
            else:
                y = X[-1]
            overlap[jj][ii] = y
    ops = pp('012')
    ans = len(S[0]) + len(S[1]) + len(S[2])
    best = ans
    for op in ops:
        tmp = ans
        tmp -= overlap[int(op[0])][int(op[1])]
        tmp -= overlap[int(op[1])][int(op[2])]
        best = min(best, tmp)
    return best
print(solve())

Solution (Python):
""""""
import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
import time
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        import os
        self.os = os
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            self.os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string
start_time = time.time()

def getInts():
    return [int(s) for s in input().split()]

def getInt():
    return int(input())

def getStrs():
    return [s for s in input().split()]

def getStr():
    return input()

def listStr():
    return list(input())

def getMat(n):
    return [getInts() for _ in range(n)]

def isInt(s):
    return '0' <= s[0] <= '9'
MOD = 998244353
''
from itertools import permutations as pp

def solve():
    S = [listStr(), listStr(), listStr()]
    overlap = [[0 for j in range(3)] for i in range(3)]

    def calc(x, y):
        (s1, s2) = (S[x], S[y])
        if not s1:
            return [0]
        if not s2:
            return [0]
        N = len(s1)
        T = [0] * N
        pos = 1
        cnd = 0
        while pos < N:
            if s1[pos] == s1[cnd]:
                cnd += 1
                T[pos] = cnd
            else:
                while cnd:
                    cnd = T[cnd - 1]
                    if s1[pos] == s1[cnd]:
                        cnd += 1
                        T[pos] = cnd
                        break
            pos += 1
        pos = 0
        cnd = 0
        N2 = len(s2)
        T2 = [0] * N2
        while pos < N2:
            if s2[pos] == s1[cnd]:
                cnd += 1
                T2[pos] = cnd
            else:
                while cnd:
                    cnd = T[cnd - 1]
                    if s2[pos] == s1[cnd]:
                        cnd += 1
                        T2[pos] = cnd
                        break
            if cnd == N:
                cnd = T[cnd - 1]
            pos += 1
        return T2
    for ii in range(3):
        for jj in range(ii + 1, 3):
            X = calc(ii, jj)
            if max(X) == len(S[ii]):
                S[ii] = ''
                y = 0
            else:
                y = X[-1]
            overlap[ii][jj] = y
            X = calc(jj, ii)
            if max(X) == len(S[jj]):
                S[jj] = ''
                y = 0
            else:
                y = X[-1]
            overlap[jj][ii] = y
    ops = pp('012')
    ans = len(S[0]) + len(S[1]) + len(S[2])
    best = ans
    for op in ops:
        tmp = ans
        tmp -= overlap[int(op[0])][int(op[1])]
        tmp -= overlap[int(op[1])][int(op[2])]
        best = min(best, tmp)
    return best
print(solve())