結果
| 問題 |
No.430 文字列検索
|
| コンテスト | |
| ユーザー |
 tomerun
|
| 提出日時 | 2016-10-04 17:26:05 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 347 ms / 2,000 ms |
| コード長 | 6,198 bytes |
| コンパイル時間 | 2,763 ms |
| コンパイル使用メモリ | 84,092 KB |
| 実行使用メモリ | 50,008 KB |
| 最終ジャッジ日時 | 2024-11-10 00:09:06 |
| 合計ジャッジ時間 | 7,535 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 14 |
ソースコード
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;
}
}