結果
問題 | No.430 文字列検索 |
ユーザー |
|
提出日時 | 2016-10-19 02:41:15 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 134 ms / 2,000 ms |
コード長 | 5,072 bytes |
コンパイル時間 | 4,183 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 41,640 KB |
最終ジャッジ日時 | 2024-11-10 00:11:01 |
合計ジャッジ時間 | 5,664 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 14 |
ソースコード
import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.Arrays; import java.util.Queue; public class SakuraPoetry { static InputStream is; static PrintWriter out; static String INPUT = ""; public static void main(String[] args) throws Exception { new SakuraPoetry().run(); } void solver() { TrieByList trie = new TrieByList(); char[] s = ns().toLowerCase().toCharArray(); int m = ni(); while (m-- > 0) { trie.add(ns().toLowerCase().toCharArray()); } trie.buildFailure(); out.println(trie.countHit(s)); } class TrieByList { Node root = new Node(0, (char) 0); 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 appendChild(Node n) { if (p == 0) { child = new Node[1]; } else if (p + 1 > child.length) { child = Arrays.copyOf(child, 2 * child.length); } int z = n.c - 'a'; int zind = Integer.bitCount(ptn << 31 - z); System.arraycopy(child, zind, child, zind + 1, p - zind); ptn |= 1 << z; child[zind] = n; p++; } } void buildFailure() { root.fail = null; Queue<Node> q = new ArrayDeque<>(); 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 next = to.search(ch.c); if (next != null) { ch.fail = next; ch.hit += next.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[] 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; } } void run() { is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); solver(); out.flush(); } static long nl() { try { long num = 0; boolean minus = false; while ((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-')) ; if (num == '-') { num = 0; minus = true; } else { num -= '0'; } while (true) { int b = is.read(); if (b >= '0' && b <= '9') { num = num * 10 + (b - '0'); } else { return minus ? -num : num; } } } catch (IOException e) { } return -1; } static char nc() { try { int b = skip(); if (b == -1) return 0; return (char) b; } catch (IOException e) { } return 0; } static double nd() { try { return Double.parseDouble(ns()); } catch (Exception e) { } return 0; } static String ns() { try { int b = skip(); StringBuilder sb = new StringBuilder(); if (b == -1) return ""; sb.append((char) b); while (true) { b = is.read(); if (b == -1) return sb.toString(); if (b <= ' ') return sb.toString(); sb.append((char) b); } } catch (IOException e) { } return ""; } public static char[] ns(int n) { char[] buf = new char[n]; try { int b = skip(), p = 0; if (b == -1) return null; buf[p++] = (char) b; while (p < n) { b = is.read(); if (b == -1 || b <= ' ') break; buf[p++] = (char) b; } return Arrays.copyOf(buf, p); } catch (IOException e) { } return null; } public static byte[] nse(int n) { byte[] buf = new byte[n]; try { int b = skip(); if (b == -1) return null; is.read(buf); return buf; } catch (IOException e) { } return null; } static int skip() throws IOException { int b; while ((b = is.read()) != -1 && !(b >= 33 && b <= 126)) ; return b; } static boolean eof() { try { is.mark(1000); int b = skip(); is.reset(); return b == -1; } catch (IOException e) { return true; } } static int ni() { try { int num = 0; boolean minus = false; while ((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-')) ; if (num == '-') { num = 0; minus = true; } else { num -= '0'; } while (true) { int b = is.read(); if (b >= '0' && b <= '9') { num = num * 10 + (b - '0'); } else { return minus ? -num : num; } } } catch (IOException e) { } return -1; } static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } }