专栏首页机器学习入门4.7字符串上的动态规划

4.7字符串上的动态规划

挑战程序竞赛系列(65):4.7字符串上的动态规划(3)


题意:

基因工程:给定m个子串,求构造长n的母串的方案数。母串中每个字符都至少来自一个子串。

中文的解释有点含糊,不如看原文公式:

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.

所以说w中的每个字符,都能找到一个左边界和右边界属于某个子串即可。

思路:

dp[i][j] 在状态i下,后缀未能匹配的长度为j的方案数
所以,我们求的是各种状态下dp[i][0]之和

这里省去了阶段,因为下一阶段总由上一阶段生成,没必要重复记录。

代码很巧妙,记录了后缀的最大长度,解决了重叠问题。

如果后缀(状态)中不存在子串,最大长度为0,而我们知道一个新串一定从0开始构建的。

所以,对于后缀中最大长度为0的这些状态一定是转移的中间态,而一旦在转移过程中,状态的最大长度非零。

说明当中存在了子串,那么既然能够抵达该状态,长度为newNeed的新串一定属于该状态的某个最大子串中。

代码如下:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
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<>();
        pfx.add("");
        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) {
                pfx.add(p[i].substring(0, 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;
    }

    void read() {
        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();
        read();
        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 {
        BufferedReader br;
        StringTokenizer st;
        boolean hasNext;

        public FastScanner(InputStream is) throws IOException {
            br = new BufferedReader(new InputStreamReader(is));
            hasNext = true;
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } 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。

    用户1147447
  • POJ 刷题系列:1753. Flip Game

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

    用户1147447
  • POJ 刷题系列:2485. Highways

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

    用户1147447
  • HDU 1083 Courses(二分图最大匹配)

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

    Ch_Zaqdt
  • LeetCode第166场周赛题解

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

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

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

    张泽旭
  • 程序员进阶之算法练习(三十五)LeetCode专场

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

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

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

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

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

    Angel_Kitty
  • “盛大游戏杯”第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...

    Angel_Kitty

扫码关注云+社区

领取腾讯云代金券