結果
問題 | No.430 文字列検索 |
ユーザー |
![]() |
提出日時 | 2016-10-02 23:18:50 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,709 ms / 2,000 ms |
コード長 | 5,187 bytes |
コンパイル時間 | 4,291 ms |
コンパイル使用メモリ | 81,056 KB |
実行使用メモリ | 65,156 KB |
最終ジャッジ日時 | 2024-11-10 00:03:42 |
合計ジャッジ時間 | 15,654 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 14 |
ソースコード
package No400番台;import java.io.ByteArrayInputStream;import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.util.ArrayList;import java.util.Arrays;public class Q430 {static InputStream is;static PrintWriter out;static String INPUT = "";public static void main(String[] args) throws Exception {new Q430().run();}void solver() {char[] s = ns().toCharArray();int n = s.length;// long[] mod = { 1000000009, 1000000007 };long[] mod = { 1000000009 };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();ArrayList<Long>[][] list = new ArrayList[mod.length][11];for (int mode = 0; mode < mod.length; mode++) {for (int i = 0; i <= 10; i++) {list[mode][i] = new ArrayList<Long>();}}for (int len = 1; len <= 10; len++) {for (int i = 0; i <= n - len; i++) {for (int mode = 0; mode < mod.length; mode++) {long val = (hash[mode][i] - ((n - len == i) ? 0 : hash[mode][i + len] * pow[mode][len]) % mod[mode]+ mod[mode]) % mod[mode];list[mode][len].add(val);}}}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];if (hash_c[mode] > mod[mode])hash_c[mode] %= mod[mode];}}for (int mode = 0; mode < mod.length; mode++) {long val = hash_c[mode];list[mode][c.length].sort(null);int imp = list[mode][c.length].size();int pos = -1;while (imp - pos > 1) {int mid = (imp + pos) / 2;if (list[mode][c.length].get(mid) > val) {imp = mid;} else {pos = mid;}}if (pos!=-1&&list[mode][c.length].get(pos) == val) {ans++;while (pos - 1 >= 0 && list[mode][c.length].get(pos - 1) == val) {pos--;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));}}