結果
問題 | No.430 文字列検索 |
ユーザー | pop_o |
提出日時 | 2024-09-21 13:10:27 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,484 bytes |
コンパイル時間 | 2,533 ms |
コンパイル使用メモリ | 208,260 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-10 01:13:07 |
合計ジャッジ時間 | 2,832 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
ソースコード
#include<bits/stdc++.h> using namespace std; // https://atcoder.jp/contests/abc362/submissions/57921480 // https://atcoder.jp/contests/practice2/submissions/57923167 // return suffix array (size: n+1) beginning with the empty string template<typename T> vector<int> suffix_array(const T &s) { int t = 1, n = (int) s.size(); vector<int> tmp(n+1), rank(n+1), sa(n+1); auto comp = [&] (int i, int j) -> bool { if (rank[i] != rank[j]) { return rank[i] < rank[j]; } else { return (i + t <= n ? rank[i + t]: -1) < (j + t <= n ? rank[j + t]: -1); } }; for (int i = 0; i <= n; i++) { sa[i] = i; rank[i] = i < n ? s[i]: -1; } for (; t <= n; t <<= 1) { sort(sa.begin(), sa.end(), comp); tmp[sa[0]] = 0; for (int i = 1; i <= n; i++) { tmp[sa[i]] = tmp[sa[i-1]] + (comp(sa[i-1], sa[i]) ? 1: 0); } for (int i = 0; i <= n; i++) { rank[i] = tmp[i]; } } return sa; } template<typename T> vector<int> lcp_array(const T &s, const vector<int> &sa) { int n = (int) s.size(), h = 0; vector<int> rank(n+1), lcp(n+1, 0); for (int i = 0; i <= n; i++) { rank[sa[i]] = i; } for (int i = 0; i < n; i++) { int j = sa[rank[i]-1]; if (h > 0) h--; for (;j+h < n && i+h < n; h++) { if (s[j+h] != s[i+h]) break; } lcp[rank[i]-1] = h; } return lcp; } // return the number of t template<typename T, typename S = char> int count_string(T &t, const T &s, const vector<int> &sa) { int n = (int)s.size(); int ok1 = -1, ng1 = n+1, ok2 = -1, ng2 = n+1; while (ng1 - ok1 > 1) { int mid = (ok1 + ng1) / 2; int m = min((int)t.size(), n - sa[mid]); if (s.substr(sa[mid], m) < t) { ok1 = mid; } else { ng1 = mid; } } t.push_back('~'); while (ng2 - ok2 > 1) { int mid = (ok2 + ng2) / 2; int m = min((int)t.size(), n - sa[mid]); if (s.substr(sa[mid], m) < t) { ok2 = mid; } else { ng2 = mid; } } t.pop_back(); return ok2 - ok1; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; cin >> s; vector<int> sa = suffix_array(s); int m; cin >> m; for (;m--;) { string c; cin >> c; cout << count_string(c, s, sa) << "\n"; } }