阿祁的部落格

CSES 1731 - Word Combinations 解題心得( 題目 )

解題概念:Trie DP

解題方法:這題利用trie加速字串比對，並且我們定義dp[i]表示組成從i~最後字串部分的解，每一步可O(n)，總時間複雜度為O(n^2)。

Java參考程式碼(更好意見可留言於下方，謝謝!):

//Author:En Chi Tsung(欉恩祁)

//Date:2022/02/16

import java.io.*;

import java.util.*;

public class cses1731 {

    public static int ret,r;

    public static String str,ma;

    public static long[] dp=new long[5005];

    public static final int p=(int)Math.pow(10,9)+7;

    public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));    

    public static void main(String[] args) throws Exception{

        ma=br.readLine();

        final int n=Integer.parseInt(br.readLine());

        Node trie=new Node();    

        dp[ma.length()]=1;

        for(int i=0;i<n;i++) {

            str=br.readLine();

            trie.Add(0);

        }

        for(int i=ma.length()-1;i>=0;i--) {

            dp[i]=trie.Query(i);

        }

        System.out.println(dp[0]);

    }

}



class Node{

    boolean end=false;

    Node[] n=new Node[26];

    int c,cnt;

    void Add(int x) {

        if(x==cses1731.str.length()) {

            end=true;

            return;

        }

        c=cses1731.str.charAt(x)-'a';

        if(n[c]==null) {

            n[c]=new Node();

        }

        n[c].Add(x+1);

    }

    int Query(int x){

        cnt=0;

        if(end)cnt+=cses1731.dp[x];

        if(x==cses1731.ma.length()) {

            return cnt;

        }

        c=cses1731.ma.charAt(x)-'a';

        if(n[c]==null) {

            return cnt;


        }
        return (cnt+n[c].Query(x+1))%cses1731.p;

    }

}