結果

問題 No.430 文字列検索
ユーザー 37zigen37zigen
提出日時 2016-10-28 14:48:37
言語 Java21
(openjdk 21)
結果
AC  
実行時間 277 ms / 2,000 ms
コード長 2,265 bytes
コンパイル時間 3,980 ms
コンパイル使用メモリ 80,048 KB
実行使用メモリ 47,532 KB
最終ジャッジ日時 2024-11-10 00:12:04
合計ジャッジ時間 8,518 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 136 ms
40,980 KB
testcase_01 AC 269 ms
47,532 KB
testcase_02 AC 257 ms
45,364 KB
testcase_03 AC 257 ms
44,528 KB
testcase_04 AC 124 ms
41,364 KB
testcase_05 AC 135 ms
41,084 KB
testcase_06 AC 137 ms
41,296 KB
testcase_07 AC 137 ms
41,512 KB
testcase_08 AC 199 ms
41,896 KB
testcase_09 AC 152 ms
41,244 KB
testcase_10 AC 156 ms
41,688 KB
testcase_11 AC 271 ms
46,340 KB
testcase_12 AC 276 ms
46,412 KB
testcase_13 AC 277 ms
46,844 KB
testcase_14 AC 272 ms
46,908 KB
testcase_15 AC 260 ms
46,708 KB
testcase_16 AC 271 ms
46,160 KB
testcase_17 AC 270 ms
45,868 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package yukicoder;

import java.util.*;

public class Q430 {
	public static void main(String[] args) {
		new Q430().run();
	}

	void run() {
		solver();
	}

	void solver() {
		TrieByList trie = new TrieByList();
		Scanner sc = new Scanner(System.in);
		char[] s = sc.next().toCharArray();
		int m = sc.nextInt();
		while (m-- > 0) {
			trie.add(sc.next().toCharArray());
		}
		trie.buildFailure();
		System.out.println(trie.countHit(s));
	}

	class TrieByList {
		Node root = new Node(0, (char) -1);
		int gen = 1;

		class Node {
			int id;
			char c;
			Node[] child = null;
			int p = 0;
			int ptn = 0;
			Node fail;
			int hit = 0;

			public Node(int id, char c) {
				this.id = id;
				this.c = c;
			}

			Node search(char c) {
				if (ptn << 31 - (c - 'a') < 0)
					return child[Integer.bitCount(ptn << 31 - (c - 'a')) - 1];
				else
					return null;
			}

			void append(Node ch) {
				if (p == 0)
					child = new Node[1];
				else if (p + 1 > child.length)
					child = Arrays.copyOf(child, child.length * 2);
				int zind = Integer.bitCount(ptn << 31 - (ch.c - 'a'));
				System.arraycopy(child, zind, child, zind + 1, p - zind);
				ptn |= 1 << (ch.c - 'a');
				child[zind] = ch;
				++p;
			}
		}

		void buildFailure() {
			Queue<Node> q = new ArrayDeque<>();
			root.fail = null;
			q.add(root);
			while (!q.isEmpty()) {
				Node cur = q.poll();
				outer: for (int i = 0; i < cur.p; ++i) {
					q.add(cur.child[i]);
					for (Node to = cur.fail; to != null; to = to.fail) {
						Node next = to.search(cur.child[i].c);
						if (next != null) {
							cur.child[i].hit += next.hit;
							cur.child[i].fail = next;
							continue outer;
						}
					}
					cur.child[i].fail = root;
				}
			}
		}

		void add(char[] s) {
			Node pre = null;
			Node cur = root;
			for (char c : s) {
				pre = cur;
				cur = pre.search(c);
				if (cur == null) {
					cur = new Node(gen++, c);
					pre.append(cur);
				}
			}
			++cur.hit;
		}

		int countHit(char[] s) {
			Node cur = root;
			int hit = 0;
			outer: for (char c : s) {
				for (; cur != null; cur = cur.fail) {
					Node next = cur.search(c);
					if (next != null) {
						hit += next.hit;
						cur = next;
						continue outer;
					}
				}
				cur = root;
			}
			return hit;
		}
	}
}
0