結果

問題 No.430 文字列検索
コンテスト
ユーザー 37zigen
提出日時 2016-10-18 12:49:08
言語 Java
(openjdk 23)
結果
AC  
実行時間 228 ms / 2,000 ms
コード長 2,654 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,010 ms
コンパイル使用メモリ 79,928 KB
実行使用メモリ 47,436 KB
最終ジャッジ日時 2024-11-10 00:10:37
合計ジャッジ時間 7,037 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.Scanner;

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

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

	}

	class TrieByList {
		Node root = new Node(0, (char) 0);
		int gen = 1;// ノードの数。

		class Node {
			int id;// 0indexed
			char c;
			Node[] child = null;
			int ptn = 0;// 0indexedで各アルファベットが存在するかどうかを格納。
			int p = 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 appendChild(Node n) {
				if (p == 0) {
					child = new Node[1];
				} else if (p + 1 > child.length) {
					child = Arrays.copyOf(child, child.length * 2);
				}
				// zはchildには格納されていない前提
				int z = n.c - 'A';
				int nind = Integer.bitCount(ptn << 31 - z);// c以下の番号のアルファベットがいくつ格納されているか
				ptn |= 1 << z;
				// nindは0indexed
				System.arraycopy(child, nind, child, nind + 1, p - nind);// http://www.javaroad.jp/java_array2.htm
				child[nind] = n;
				p++;
			}
		}

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

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

		int countHit(char[] q) {
			Node cur = root;
			int hit = 0;
			outer: for (char c : q) {
				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