Problem:
Connect You are playing a solitaire puzzle called "Connect", which uses several letter tiles. There are R × C empty cells.
For each i  (1 ≤ i ≤ R) , you must put a string s i  (1 ≤ |s i | ≤ C) in the i -th row of the table, without changing  the letter order.
In other words, you choose an integer sequence {a j } such that 1 ≤ a 1 < a 2 < ... < a |s i | ≤ C , and put the j -th character of the string s i in the a j -th column (1 ≤ j ≤ |s i |) . For example, when C = 8 and s i = "ICPC", you can put s i like followings. I_C_P_C_
ICPC____
_IC___PC '_' represents an empty cell. For each non-empty cell x , you get a point equal to the number of adjacent cells which have the same character as x .
Two cells are adjacent if they share an edge. Calculate the maximum total point you can get. Input The first line contains two integers R and C  (1 ≤ R ≤ 128, 1 ≤ C ≤ 16) . Then R lines follow, each of which contains s i  (1 ≤ |s i | ≤ C) .
All characters of s i are uppercase letters. Output Output the maximum total point in a line. Sample Input 1 2 4
ACM
ICPC Output for the Sample Input 1 2 Sample Input 2 2 9
PROBLEMF
CONNECT Output for the Sample Input 2 6 Sample Input 3 4 16
INTERNATIONAL
COLLEGIATE
PROGRAMMING
CONTEST Output for the Sample Input 3 18

Solution (Python):

import sys
readline = sys.stdin.readline
write = sys.stdout.write

def gen(N, K):
    if K == 0:
        yield 0
        return
    v = (1 << K) - 1
    N2 = (1 << N)
    while v < N2:
        yield v
        x = v & -v; y = v + x
        v = ((v & ~y) // x >> 1) | y

def solve():
    R, C = map(int, readline().split())
    S = [readline().strip() for i in range(R)]
    C2 = (1 << C)
    bc = [0]*C2
    for state in range(1, C2):
        bc[state] = bc[state ^ (state & -state)] + 1

    LI = [None]*(C+1)
    RI = [None]*(C+1)
    for sl in range(C+1):
        r0 = [None]*(C+1)
        r1 = [None]*(C+1)
        for j in range(C+1):
            sr = sl - (C-j)
            e0 = []
            for k in range(max(sr, 0), min(sl, C)+1):
                e0.extend(gen(j, k))
            r0[j] = e0
            r1[j] = [state << (C-j) for state in e0]
        LI[sl] = r0
        RI[sl] = r1

    dp0 = [0]*C2; dp1 = [0]*C2
    zeros = [0]*C2
    s = S[0]; sl = len(s)
    for j in range(1, C):
        dp1[:] = zeros
        b0 = (1 << (j-1))
        b1 = (1 << j)
        for state in LI[sl][j]:
            ll = bc[state]
            dp1[state] = dp0[state]
            if ll < sl:
                if state & b0 and s[ll-1] == s[ll]:
                    dp1[state | b1] = dp0[state] + 2
                else:
                    dp1[state | b1] = dp0[state]
        dp0, dp1 = dp1, dp0
    for i in range(1, R):
        p = S[i-1]; pl = len(p)
        s = S[i]; sl = len(s)
        for j in range(C):
            dp1[:] = zeros
            b0 = (1 << (j-1)) if j else 0
            b1 = (1 << j)
            L0 = LI[sl][j]; R0 = RI[pl][C-j-1]
            for state1 in L0:
                ll = bc[state1]
                if ll < sl:
                    c = s[ll]
                    for state2 in R0:
                        rl = bc[state2]
                        state = state1 | state2
                        n_state = state | b1

                        if j < C-1:
                            dp1[state] = max(dp0[state], dp0[n_state]) if rl < pl else dp0[state]
                        r1 = max(dp0[state], (dp0[n_state] + 2 if (p[-rl-1] == c) else dp0[n_state])) if rl < pl else dp0[state]
                        if state & b0 and s[ll-1] == c:
                            dp1[n_state] = r1 + 2
                        else:
                            dp1[n_state] = r1
                else:
                    for state2 in R0:
                        state = state1 | state2
                        if bc[state2] < pl:
                            dp1[state] = max(dp0[state], dp0[state | b1])
                        else:
                            dp1[state] = dp0[state]
            dp0, dp1 = dp1, dp0
    write("%d\n" % max(dp0))
solve()