https://codeforces.com/problemset/problem/49/E

题意：

DNA序列的一个字符会被替换成另外的两个。变化a[i] → b[i] c[i]

 每一种变化均可以无限次发生。总共有n种允许的变化。 科学家们表示，

 如果一个DNA序列s3 在整个进化过程中可以最终变为s1  和s2 ，

 那么DNA序列分别为s1  和s2 的两个生物就会有一个共同祖先。现在给出s1

  和s2，你的任务是弄清楚分别拥有这两种DNA序列的生物是否有共同祖先。如果存在，

  你需要找出所有共同祖先中最短长度。

 题解：

ok[s][st][ed]|= 1<<c-'a'   代表 字符串区间s[st,ed]可以由单一的字母c变换得到，

 c可以有多种选项，ok[s][st][ed]为字符状态压缩。

dp[i][j]代表 对于S串前i个元素和对于T串前j个元素最短的初始字符串长度。

状态转移

dp[i][j]=min(dp[i][j],dp[i−k1][j−k2]+1)(k1，k2表示s1和s2最后分别连续k1和k2的长度可以缩成同一字母)