結果

問題 No.430 文字列検索
ユーザー tomeruntomerun
提出日時 2016-10-04 17:26:05
言語 Java21
(openjdk 21)
結果
AC  
実行時間 398 ms / 2,000 ms
コード長 6,198 bytes
コンパイル時間 2,492 ms
コンパイル使用メモリ 80,780 KB
実行使用メモリ 61,688 KB
最終ジャッジ日時 2023-08-15 17:42:33
合計ジャッジ時間 8,423 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 126 ms
55,764 KB
testcase_01 AC 341 ms
60,048 KB
testcase_02 AC 323 ms
61,420 KB
testcase_03 AC 313 ms
59,868 KB
testcase_04 AC 124 ms
55,716 KB
testcase_05 AC 124 ms
55,972 KB
testcase_06 AC 123 ms
56,128 KB
testcase_07 AC 124 ms
55,640 KB
testcase_08 AC 258 ms
58,880 KB
testcase_09 AC 135 ms
55,620 KB
testcase_10 AC 159 ms
55,996 KB
testcase_11 AC 365 ms
60,184 KB
testcase_12 AC 397 ms
60,376 KB
testcase_13 AC 398 ms
61,688 KB
testcase_14 AC 389 ms
59,860 KB
testcase_15 AC 390 ms
61,588 KB
testcase_16 AC 367 ms
60,172 KB
testcase_17 AC 360 ms
61,268 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			String S = sc.next();
			SuffixArray sa = SuffixArray.build(S);
			int M = sc.nextInt();
			int ans = 0;
			for (int i = 0; i < M; ++i) {
				String C = sc.next();
				int[] r = range(sa, S, C);
				ans += r[1] - r[0];
			}
			System.out.println(ans);
		}
	}

	static int[] range(SuffixArray sa, String original, String str) {
		int[] ret = new int[2];
		{
			int lo = 0;
			int hi = original.length() + 1;
			while (hi - lo > 1) {
				int mid = (lo + hi) / 2;
				int comp = compare(sa.suffixArray[mid], original, str);
				if (comp >= 0) {
					hi = mid;
				} else {
					lo = mid;
				}
			}
			ret[0] = lo;
		}
		{
			int lo = 0;
			int hi = original.length() + 1;
			while (hi - lo > 1) {
				int mid = (lo + hi) / 2;
				int comp = compare(sa.suffixArray[mid], original, str);
				if (comp > 0) {
					hi = mid;
				} else {
					lo = mid;
				}
			}
			ret[1] = lo;
		}
		return ret;
	}

	static int compare(int pos, String original, String str) {
		for (int i = 0; i < str.length(); ++i) {
			if (pos + i == original.length()) return -1;
			char c1 = original.charAt(pos + i);
			char c2 = str.charAt(i);
			if (c1 != c2) {
				return Character.compare(c1, c2);
			}
		}
		return 0;
	}

}

class SuffixArray {

	private static final boolean DEBUG = false;

	/** contains suffix array indexes including sentinel */
	int[] suffixArray;

	private SuffixArray(String str) {
		int[] S = new int[str.length() + 1];
		int maxChar = 0;
		for (int i = 0; i < str.length(); ++i) {
			S[i] = str.charAt(i);
			maxChar = Math.max(maxChar, S[i]);
		}
		S[str.length()] = 0; // sentinel
		this.suffixArray = rec(S, maxChar);
	}

	private int[] rec(int[] S, int maxChar) {
		int N = S.length;
		BitSet isStype = new BitSet(N);
		isStype.set(N - 1);
		for (int i = N - 2; i >= 0; --i) {
			if (S[i] == S[i + 1]) {
				isStype.set(i, isStype.get(i + 1));
			} else {
				isStype.set(i, S[i] < S[i + 1]);
			}
		}
		ArrayList<Integer> lmsIndex = new ArrayList<>();
		for (int i = 0; i < N - 1; ++i) {
			if (!isStype.get(i) && isStype.get(i + 1)) lmsIndex.add(i + 1);
		}
		if (DEBUG) System.err.println("P:" + lmsIndex);
		int[] SA = new int[N];
		Arrays.fill(SA, -1);

		// induced sort for LMS strings
		int[] bucketTail = getBucketTail(S, maxChar);
		int[] bucketPos = bucketTail.clone();
		for (int i = 0; i < lmsIndex.size(); ++i) {
			int p = lmsIndex.get(i);
			int firstChar = S[p];
			bucketPos[firstChar]--;
			SA[bucketPos[firstChar]] = p;
		}
		inducedSort(S, isStype, SA, bucketTail.clone());

		// rename (reuse SA as buffer to sort P)
		int[] S1 = new int[lmsIndex.size()];
		int n1 = 1;
		for (int i = 1; i < N; ++i) {
			if (isLMS(isStype, SA[i])) {
				SA[n1++] = SA[i];
			}
		}
		assert (n1 == lmsIndex.size());
		Arrays.fill(SA, n1, N, -1);
		int name = 0;
		for (int i = 0; i < n1; ++i) {
			if (i != 0 && !isEqualLMS(S, isStype, SA[i - 1], SA[i])) ++name;
			SA[n1 + SA[i] / 2] = name;
		}
		for (int i = N - 1, j = n1; j > 0; --i) {
			if (SA[i] != -1) S1[--j] = SA[i];
		}
		if (DEBUG) System.err.println("S1:" + Arrays.toString(S1) + " name:" + name + " n1:" + n1);

		int[] SA1;
		if (name + 1 == n1) {
			// build SA directly
			SA1 = new int[n1];
			for (int i = 0; i < n1; ++i) {
				SA1[S1[i]] = i;
			}
		} else {
			// recursive call
			SA1 = rec(S1, name);
		}
		if (DEBUG) System.err.println("SA1:" + Arrays.toString(SA1));

		// induce whole SA from sorted LMS strings
		Arrays.fill(SA, -1);
		bucketPos = bucketTail.clone();
		for (int i = SA1.length - 1; i >= 0; --i) {
			int p = lmsIndex.get(SA1[i]);
			int firstChar = S[p];
			bucketPos[firstChar]--;
			SA[bucketPos[firstChar]] = p;
		}
		inducedSort(S, isStype, SA, bucketTail.clone());
		if (DEBUG) System.err.println("SA:" + Arrays.toString(SA));

		return SA;
	}

	private void inducedSort(int[] S, BitSet isStype, int[] SA, int[] bucketTail) {
		// step 2
		int[] bucketHead = new int[bucketTail.length];
		for (int i = 1; i < bucketHead.length; ++i) {
			bucketHead[i] = bucketTail[i - 1];
		}
		int N = S.length;
		for (int i = 0; i < N; ++i) {
			if (SA[i] <= 0) continue;
			if (!isStype.get(SA[i] - 1)) {
				int firstChar = S[SA[i] - 1];
				SA[bucketHead[firstChar]] = SA[i] - 1;
				bucketHead[firstChar]++;
			}
		}

		// step 3
		for (int i = N - 1; i >= 0; --i) {
			if (SA[i] <= 0) continue;
			if (isStype.get(SA[i] - 1)) {
				int firstChar = S[SA[i] - 1];
				bucketTail[firstChar]--;
				SA[bucketTail[firstChar]] = SA[i] - 1;
			}
		}
	}

	private boolean isEqualLMS(int[] S, BitSet isStype, int p1, int p2) {
		for (int i = 0;; ++i) {
			if (S[p1 + i] != S[p2 + i]) return false;
			if (isStype.get(p1 + i) != isStype.get(p2 + i)) return false;
			if (i > 0) {
				if (isLMS(isStype, p1 + i)) {
					return isLMS(isStype, p2 + i);
				}
				if (isLMS(isStype, p2 + i)) return false;
			}
		}
	}

	private static int[] getBucketTail(int[] S, int maxChar) {
		int[] bucketTail = new int[maxChar + 1];
		for (int i = 0; i < S.length; ++i) {
			bucketTail[S[i]]++;
		}
		for (int i = 1; i <= maxChar; ++i) {
			bucketTail[i] += bucketTail[i - 1];
		}
		return bucketTail;
	}

	private static boolean isLMS(BitSet isStype, int p) {
		if (p == 0) return false;
		return isStype.get(p) && !isStype.get(p - 1);
	}

	/**
	 *  create Suffix Array using SA-IS algorithm
	 *  @param str
	 *         target string
	 */
	public static SuffixArray build(String str) {
		return new SuffixArray(str);
	}

	public static int[] buildNaive(String str) {
		final int[] S = new int[str.length() + 1];
		for (int i = 0; i < str.length(); ++i) {
			S[i] = str.charAt(i);
		}
		S[str.length()] = 0; // sentinel
		Integer[] SA = new Integer[S.length];
		for (int i = 0; i < SA.length; ++i) {
			SA[i] = i;
		}
		Arrays.sort(SA, (Integer i, Integer j) -> {
			for (int pos = 0;; ++pos) {
				if (S[i + pos] != S[j + pos]) return Integer.compare(S[i + pos], S[j + pos]);
			}
		});

		int[] ret = new int[SA.length];
		for (int i = 0; i < ret.length; ++i) {
			ret[i] = SA[i];
		}
		return ret;
	}

}
0