Codeforces Round #299 Div2 E: Tavas and Malekas (Z Algorithm)

問題

codeforces.com

解法

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;
	}

}