結果
問題 | No.430 文字列検索 |
ユーザー |
![]() |
提出日時 | 2016-10-02 22:46:32 |
言語 | Java (openjdk 23) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,388 bytes |
コンパイル時間 | 2,224 ms |
コンパイル使用メモリ | 78,844 KB |
実行使用メモリ | 48,416 KB |
最終ジャッジ日時 | 2024-11-10 00:02:21 |
合計ジャッジ時間 | 5,787 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 4 |
other | AC * 1 TLE * 1 -- * 12 |
ソースコード
import java.io.ByteArrayInputStream;import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.util.Arrays;public class Main {static InputStream is;static PrintWriter out;static String INPUT = "";public static void main(String[] args) throws Exception {new Main().run();}void solver() {char[] s = ns().toCharArray();int n = s.length;long[] mod = { 1000000009, 1000000007 };long b = 29;long[][] hash = new long[mod.length][n];long[][] pow = new long[mod.length][n];for (int mode = 0; mode < mod.length; mode++) {for (int i = 0; i < n; i++) {if (i == 0)pow[mode][i] = 1;else {pow[mode][i] = pow[mode][i - 1] * b;if (pow[mode][i] >= mod[mode])pow[mode][i] %= mod[mode];}}}for (int mode = 0; mode < mod.length; mode++) {for (int i = n - 1; i >= 0; i--) {hash[mode][i] = (s[i] - 'A') + (i == n - 1 ? 0 : hash[mode][i + 1] * b);if (hash[mode][i] > mod[mode])hash[mode][i] %= mod[mode];}}long ans = 0;int m = ni();for (; m > 0; m--) {char[] c = ns().toCharArray();long[] hash_c = new long[mod.length];if (c.length > n)continue;for (int mode = 0; mode < mod.length; mode++) {for (int i = 0; i < c.length; i++) {hash_c[mode] += (c[i] - 'A') * pow[mode][i];hash_c[mode] %= mod[mode];}}for (int i = 0; i <= n - c.length; i++) {boolean f = true;for (int mode = 0; mode < mod.length; mode++) {if ((hash[mode][i]- ((n - c.length == i) ? 0 : hash[mode][i + c.length] * pow[mode][c.length]) % mod[mode]+ mod[mode]) % mod[mode] != hash_c[mode]) {f = false;break;}}if (f) {ans++;}}}out.println(ans);}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));}}