Problem:
Problem F: City Merger Recent improvements in information and communication technology have made it possible to provide municipal service to a wider area more quickly and with less costs. Stimulated by this, and probably for saving their not sufficient funds, mayors of many cities started to discuss on mergers of their cities. There are, of course, many obstacles to actually put the planned mergers in practice. Each city has its own culture of which citizens are proud. One of the largest sources of friction is with the name of the new city. All citizens would insist that the name of the new city should have the original name of their own city at least as a part of it. Simply concatenating all the original names would, however, make the name too long for everyday use. You are asked by a group of mayors to write a program that finds the shortest possible name for the new city that includes all the original names of the merged cities. If two or more cities have common parts, they can be overlapped. For example, if "FUKUOKA", "OKAYAMA", and "YAMAGUCHI" cities are to be merged, "FUKUOKAYAMAGUCHI" is such a name that include all three of the original city names. Although this includes all the characters of the city name "FUKUYAMA" in this order, it does not appear as a consecutive substring, and thus "FUKUYAMA" is not considered to be included in the name. Input The input is a sequence of datasets. Each dataset begins with a line containing a positive integer n ( n ≤ 14), which denotes the number of cities to be merged. The following n lines contain the names of the cities in uppercase alphabetical letters, one in each line. You may assume that none of the original city names has more than 20 characters. Of course, no two cities have the same name. The end of the input is indicated by a line consisting of a zero. Output For each dataset, output the length of the shortest possible name of the new city in one line. The output should not contain any other characters. Sample Input 3 FUKUOKA OKAYAMA YAMAGUCHI 3 FUKUOKA FUKUYAMA OKAYAMA 2 ABCDE EDCBA 4 GA DEFG CDDE ABCD 2 ABCDE C 14 AAAAA BBBBB CCCCC DDDDD EEEEE FFFFF GGGGG HHHHH IIIII JJJJJ KKKKK LLLLL MMMMM NNNNN 0 Output for the Sample Input 16 19 9 9 5 70

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def _kosa(a1, a2, b1, b2):
    x1,y1,_ = a1
    x2,y2,_ = a2
    x3,y3,_ = b1
    x4,y4,_ = b2

    tc = (x1-x2)*(y3-y1)+(y1-y2)*(x1-x3)
    td = (x1-x2)*(y4-y1)+(y1-y2)*(x1-x4)
    return tc*td < 0

def kosa(a1, a2, b1, b2):
    return _kosa(a1,a2,b1,b2) and _kosa(b1,b2,a1,a2)


def distance(x1, y1, x2, y2):
    return math.sqrt((x1-x2)**2 + (y1-y2)**2)

def distance3(p1, p2, p3):
    x1,y1,_ = p1
    x2,y2,_ = p2
    x3,y3,_ = p3

    ax = x2 - x1
    ay = y2 - y1
    bx = x3 - x1
    by = y3 - y1

    r = (ax*bx + ay*by) / (ax*ax+ay*ay)
    if r <= 0:
        return distance(x1,y1, x3,y3)
    if r >= 1:
        return distance(x2,y2, x3,y3)
    return distance(x1 + r*ax, y1 + r*ay, x3,y3)

def main():
    rr = []

    def f(n):
        a = [S() for _ in range(n)]
        b = []
        for i in range(n):
            f = True
            for j in range(n):
                if i == j:
                    continue
                if a[i] in a[j]:
                    f = False
                    break
            if f:
                b.append(a[i])
        a = b
        n = len(b)
        d = [[0]*n for _ in range(n)]
        for i in range(n):
            ai = a[i]
            for j in range(n):
                if i == j:
                    continue
                aj = a[j]
                for k in range(1, min(len(ai), len(aj))):
                    if ai[-k:] == aj[:k]:
                        d[i][j] = k

        ii = [2**i for i in range(n)]
        q = collections.defaultdict(int)
        for i in range(n):
            q[(ii[i], i)] = 0
        for _ in range(n-1):
            nq = collections.defaultdict(int)
            for i in range(n):
                t = ii[i]
                for k,v in q.items():
                    if k[0] & t:
                        continue
                    key = (k[0] | t, i)
                    nv = v + d[k[1]][i]
                    if nq[key] < nv:
                        nq[key] = nv
            q = nq
        fr = max(q.values())
        return sum(map(len, a)) - fr


    while True:
        n = I()
        if n == 0:
            break
        rr.append(f(n))
        

    return '\n'.join(map(str, rr))



print(main())

Solution (Python):
while 1:
    n = int(input())
    if n == 0:
        break
    S = [input() for i in range(n)]

    used = [1]*n

    for i in range(n):
        for j in range(n):
            if i != j and S[i].find(S[j]) > -1:
                used[j] = 0

    T = [S[i] for i in range(n) if used[i]]
    n = len(T)
    E = [[0]*n for i in range(n)]
    for i in range(n):
        for j in range(n):
            l = len(T[i])
            ti = T[i]; tj = T[j]
            pos = l
            for k in range(l):
                for p in range(l-k):
                    if ti[k+p] != tj[p]:
                        break
                else:
                    pos = k
                    break
            E[i][j] = pos
    ALL = 2**n-1
    memo = {(ALL, i): len(T[i]) for i in range(n)}
    def dfs(state, i):
        if (state, i) in memo:
            return memo[state, i]
        res = 10**18
        for j in range(n):
            if (state >> j) & 1 == 0:
                res = min(res, dfs(state | (1 << j), j) + E[i][j])
        memo[state, i] = res
        return res
    ans = 10**18
    for i in range(n):
        ans = min(ans, dfs(1 << i, i))
    print(ans)

Solution (Python):
while 1:
    n = int(input())
    if n == 0:
        break
    S = [input() for i in range(n)]

    dup = [0]*n
    for i in range(n):
        si = S[i]
        for j in range(i+1, n):
            sj = S[j]
            if si.find(sj)+1:
                dup[j] = 1
            if sj.find(si)+1:
                dup[i] = 1
    S = [S[i] for i in range(n) if not dup[i]]
    n -= sum(dup)

    P = [[0]*n for i in range(n)]
    for i in range(n):
        si = S[i]
        l = len(si)
        for j in range(n):
            sj = S[j]
            pos = l
            for k in range(l):
                if sj.startswith(si[k:]):
                    pos = k
                    break
            P[i][j] = len(sj) - (l - pos)

    ALL = 2**n - 1
    up = 300
    memo = {(ALL, i): 0 for i in range(n)}
    def dfs(state, i):
        if (state, i) in memo:
            return memo[state, i]
        res = up
        for j in range(n):
            if (state >> j) & 1 < 1:
                res = min(res, dfs(state | (1 << j), j) + P[i][j])
        memo[state, i] = res
        return res
    print(min(dfs(1 << i, i) + len(S[i]) for i in range(n)))

Solution (Python):
from collections import defaultdict
inf = float("INF")
binary = [1 << i for i in range(14)]

def main(n):

    s = [input() for _ in range(n)]
    delete = set()
    for i in range(n):
        for k in range(n):
            if i == k:
                continue
            if s[k] in s[i]:
                delete.add(k)
    n -= len(delete)
    for de in reversed(sorted(delete)):
        del s[de]

    mindist = [[inf] * n for _ in range(n)]
    lenlis = [len(s[i]) for i in range(n)]
    for i in range(n):
        mindisti = mindist[i]
        si = s[i]
        for k in range(n):
            if i == k:
                continue
            sk = s[k]
            lenk = lenlis[k]
            if sk in si:
                tmp = 0
            else:
                tmp = lenk
                for index_k in range(1, lenk + 1):
                    if sk[:index_k] == si[-index_k:]:
                        tmp = lenk - index_k
            mindisti[k] = tmp

    d = defaultdict(int)
    for i in range(n):
        d[(binary[i], i)] = len(s[i])

    for _ in range(n-1):
        nd = defaultdict(lambda: inf)
        for key, value in d.items():
            state, before = key
            mindistb = mindist[before]

            for i in range(n):
                if not (state >> i & 1):
                    if nd[(state ^ binary[i], i)] > value + mindistb[i]:
                        nd[(state ^ binary[i], i)] = value + mindistb[i]

        d = nd

    print(min(d.values()))


if __name__ == "__main__":
    while 1:
        n = int(input())
        if n:
            main(n)
        else:
            break

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve(n):
    s = [input() for i in range(n)]
    v = defaultdict(lambda : [])
    f = [1]*n
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if s[i] in s[j]:
                f[i] = 0
                break
    s = [s[i] for i in range(n) if f[i]]
    n = len(s)
    pre = [set([s[i][:j] for j in range(len(s[i])+1)]) for i in range(n)]
    for i in range(n):
        si = s[i]
        for j in range(n):
            sj = s[j]
            p = pre[j]
            if i == j:
                continue
            for k in range(len(si)):
                if s[i][k:] in p:
                    k -= 1
                    break
            l = len(si)-k-1
            v[i].append((j,len(sj)-l))
    m = 1<<n
    dp = [[float("inf")]*n for i in range(m)]
    for i in range(n):
        dp[1<<i][i] = len(s[i])
    for b in range(m):
        for i in range(n):
            if not b&(1<<i):
                continue
            d = dp[b][i]
            for j,w in v[i]:
                k = 1<<j
                if b&k:
                    continue
                nb = b|k
                nd = d+w
                if nd < dp[nb][j]:
                    dp[nb][j] = nd
    print(min(dp[m-1]))
    return


if __name__ == "__main__":
    while 1:
        n = I()
        if n == 0:
            break
        solve(n)

Solution (Python):

while True:
    n=int(input())
    if n == 0: break
    ss = [ input() for _ in range(n) ]
    ts = [ s for s in ss if all ( t.find(s) < 0 for t in ss if not (t == s)) ]
    m = len(ts)

    def overlap(c, d):
        sc = ts[c]
        sd = ts[d]
        s = len(sc)
        return max ( s - i for i in range(s+1) if sd.startswith(sc[i:]) )

    ov = [ [ overlap(c,d) for d in range(m) ] for c in range(m)]

    memo = [ [ -1 for _ in range(1<<m) ] for _ in range(m) ]
    
    
    def rec(c, cs):
        if cs == 0: return 0
        if memo[c][cs] >= 0: return memo[c][cs]
        ans= max (ov[c][d] + rec(d, cs - (1<<d)) for d in range(n) if not (((1<<d) & cs) == 0))
        memo[c][cs] = ans
        return ans

    
    
    
    
    
    
    

    maxov =  max ( rec(i, ((1<<m) - 1) - (1<<i) ) for i in range (m) )
    ans = sum (len(t) for t in ts) - maxov
    print(ans)