Submission #829300

---

Source Code Expand

import java.util.Arrays;
import java.util.Scanner;

public class Main{
	static int mod=1000000007,n,dp[];
	static String s,t[];
	static int f(int p){
		if(p==s.length()) return 1;
		if(dp[p]!=-1) return dp[p];
		int res=0;
		for(int i=0;i<n;i++){
			if(p+t[i].length()-1<s.length() && s.substring(p,p+t[i].length()).equals(t[i])) res+=f(p+t[i].length());
			res%=mod;
		}
		return dp[p]=res;
	}
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
			n=sc.nextInt();
			s=sc.next();
			t=new String[n];
			dp=new int[s.length()]; Arrays.fill(dp,-1);
			for(int i=0;i<n;i++) t[i]=sc.next();
			System.out.println(f(0));
		}
	}
}

Submission Info

Judge Result