Codeforces Round #299 Div2 E: Tavas and Malekas (Z Algorithm)
解法
Z Algorithm を使って文字列の各位置における最長の一致prefixを計算しておく。文中で文字列が交差した際に、計算した条件に合わなければ0を返せば良い。
コード
import java.util.Scanner; public class Main { private static final int MOD = 1000000007; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); String string = sc.next(); int l = string.length(); int[] z = z(string); int[] y = new int[M + 1]; for (int i = 0; i < M; i++) { y[i] = sc.nextInt() - 1; } y[M] = Integer.MAX_VALUE; sc.close(); long ans = 1; int cur = 0; for (int i = 0; i < N; i++) { if (i < y[0] || y[cur] + l <= i && i < y[cur + 1]) { ans *= 26; ans %= MOD; } else if (i == y[cur + 1]) { if (i < y[cur] + l && z[i - y[cur]] != l - (i - y[cur])) { System.out.println(0); return; } cur++; } } System.out.println(ans); } static int[] z(String string) { int N = string.length(); char[] s = string.toCharArray(); int[] z = new int[N]; int L = 0; int R = 0; for (int i = 0; i < N; i++) { if (i > R) { L = R = i; while (R < N && s[R - L] == s[R]) { R++; } z[i] = R - L; R--; } else { if (z[i - L] < R - i + 1) { z[i] = z[i - L]; } else { L = i; R++; while (R < N && s[R - L] == s[R]) { R++; } z[i] = R - L; R--; } } } return z; } }