# 4.7字符串上的动态规划

## 挑战程序竞赛系列（65）：4.7字符串上的动态规划（3）

More formally: denote by |w| the length of w, let symbols of w be numbered from 1 to |w|. Then for each position i in w there exist pair of indices l, r (1 ≤ l ≤ i ≤ r ≤ |w|) such that the substring w[l … r] equals one of the elements s1, s2, …, sm of the collection.

```dp[i][j] 在状态i下，后缀未能匹配的长度为j的方案数

```import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;

public class Main{

String INPUT = "./data/judge/201709/C086C.txt";

public static void main(String[] args) throws IOException {
new Main().run();
}

static final int MOD = 1000000009;

int solve(int n, String[] p) {
int m = p.length;

//求出每个模式的后缀
Set<String> pfx = new HashSet<>();
int maxLength = 1;
for (int i = 0; i < m; ++i) {
maxLength = Math.max(maxLength, p[i].length());
for (int j = 1; j <= p[i].length(); ++j) {
}
}

int state = pfx.size();
Map<String, Integer> mem = new HashMap<>();
int idx = 0;
for (String pf : pfx) {
mem.put(pf, idx++);
}

//更新每个状态对应的最大子串长度
int[] finish = new int[state];
for (String pf : pfx) {
for (String pp : p) {
if (pf.endsWith(pp)) {
finish[mem.get(pf)] = Math.max(finish[mem.get(pf)], pp.length());
}
}
}

//状态转移
int[][] next = new int[state][4];
for (String pf : pfx) {
for (int ch = 0; ch < 4; ++ch) {
String nxt = pf + "ATCG".charAt(ch);
while (!mem.containsKey(nxt)) {
nxt = nxt.substring(1);
}
next[mem.get(pf)][ch] = mem.get(nxt);
}
}

int[][] dp = new int[state + 16][maxLength + 16];
dp[mem.get("")][0] = 1;
for (int i = 1; i <= n; ++i) {
dp = oneStep(dp, maxLength, state, next, finish);
}

int ans = 0;
for (int i = 0; i < state; ++i) {
ans += dp[i][0];
if (ans >= MOD) ans -= MOD;
}
return ans;
}

int[][] oneStep(int[][] cnt, int maxLength, int state, int[][] next, int[] finish) {
int[][] newDp = new int[state + 16][maxLength + 16];
for (int oldState = 0; oldState < state; ++oldState) {
for (int oldNeed = 0; oldNeed < maxLength; ++oldNeed) {
for (int ch = 0; ch < 4; ++ch) {
int newState = next[oldState][ch];
int newNeed  = oldNeed + 1;
if (newNeed <= finish[newState]) newNeed = 0;
if (newNeed >= maxLength) continue;
newDp[newState][newNeed] += cnt[oldState][oldNeed];
if (newDp[newState][newNeed] >= MOD)  newDp[newState][newNeed] -= MOD;
}
}
}
return newDp;
}

int n = ni();
int m = ni();
String[] p = new String[m];
for (int i = 0; i < m; ++i) {
p[i] = ns();
}
out.println(solve(n, p));
}

FastScanner in;
PrintWriter out;

void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}

InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}

public boolean more(){
return in.hasNext();
}

public int ni(){
return in.nextInt();
}

public long nl(){
return in.nextLong();
}

public double nd(){
return in.nextDouble();
}

public String ns(){
return in.nextString();
}

public char nc(){
return in.nextChar();
}

class FastScanner {
StringTokenizer st;
boolean hasNext;

public FastScanner(InputStream is) throws IOException {
hasNext = true;
}

public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}

String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}

public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}

public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}

public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}

public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}

public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}

static class ArrayUtils {

public static void fill(int[][] f, int value) {
for (int i = 0; i < f.length; ++i) {
Arrays.fill(f[i], value);
}
}

public static void fill(int[][][] f, int value) {
for (int i = 0; i < f.length; ++i) {
fill(f[i], value);
}
}

public static void fill(int[][][][] f, int value) {
for (int i = 0; i < f.length; ++i) {
fill(f[i], value);
}
}
}
}```

0 条评论

• ### 1125. Stockbroker Grapevine

思路： 数据很水，用floyd求出任意两点之间的最短距离即可。接着遍历顶点s，求出抵达最后一个顶点的时间t，每个s对应一个t，求出t最小的s。

• ### POJ 刷题系列：1753. Flip Game

POJ 刷题系列：1753. Flip Game 传送门：POJ 1753. Filp Game 题意： 一个4*4的矩阵，每一格要么是白色，要么是黑色。现在...

• ### POJ 刷题系列：2485. Highways

思路： 还是用prim算法，很简单，思路可以参考http://blog.csdn.net/u014688145/article/details/789267...

• ### HDU 1083 Courses(二分图最大匹配)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1083

• ### LeetCode第166场周赛题解

这是LeetCode的第166场周赛的题解，不出意外的又爆炸了，前三题只做了20分钟，第4题因为题意读错了耽误了40分钟，到1小时15分钟左右才写完。排名直接1...

• ### 古典密码加密解密之多表代换

多表代换密码首先将明文M 分为由n 个字母组成的分组, , … ，对每个分组的加密为 ≡ + ( ), = , , … 其中，（A,B）是密钥，A 是 ...

• ### 程序员进阶之算法练习（三十五）LeetCode专场

LeetCode上的题目是大公司面试常见的算法题，今天的目标是拿下5道算法题： 题目1是基于链表的大数加法，既考察基本数据结构的了解，又考察在处理加法过程中的边...

• ### 【未完成】1050 螺旋矩阵 (25 分)

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### 2017年中国大学生程序设计竞赛-中南地区赛暨第八届湘潭市大学生计算机程序设计大赛题解&源码(A.高斯消元，D,模拟，E,前缀和，F,LCS，H,Prim算法，I,胡搞，J,树状数组)

A-------------------------------------------------------------------------------...

• ### “盛大游戏杯”第15届上海大学程序设计联赛夏季赛暨上海高校金马五校赛题解&&源码【A,水,B,水,C,水,D,快速幂,E,优先队列,F,暴力,G,贪心+排序,H,STL乱搞,I,尼姆博弈,J,差分dp

黑白图像直方图 发布时间: 2017年7月9日 18:30   最后更新: 2017年7月10日 21:08   时间限制: 1000ms   内存限制: 12...