Submission #1770997

---

Source Code Expand

import java.util.*;

class Main {
    static final long MOD=1000000007;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n=Integer.parseInt(scan.next());
        String s=scan.next();
        String[] t=new String[n];
        for(int i=0;i<n;++i)t[i]=scan.next();
        int l=s.length();
        long[] dp=new long[l+1];
        dp[l]=1;
        for(int i=l-1;i>=0;--i){
            long a=0;
            for(int j=0;j<n;++j){
                int u=t[j].length();
                if(u<=l-i&&t[j].equals(s.substring(i,i+u))){
                    a+=dp[i+u];
                    a%=MOD;
                }
            }
            dp[i]=a;
        }
        System.out.println(dp[0]);
    }
}

Submission Info

Judge Result