結果
問題 | No.430 文字列検索 |
ユーザー |
|
提出日時 | 2019-08-12 16:55:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 452 ms / 2,000 ms |
コード長 | 3,368 bytes |
コンパイル時間 | 2,706 ms |
コンパイル使用メモリ | 169,816 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-10 00:27:46 |
合計ジャッジ時間 | 6,462 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 14 |
ソースコード
#include <bits/stdc++.h>#define REP(i, n) for(int i = 0;i < n;i++)#define SORT(v, n) sort(v, v+n);#define VSORT(v) sort(v.begin(), v.end())#define VRSORT(v) sort(v.rbegin(), v.rend())#define ll long long#define pb(a) push_back(a)#define INF 1000000000#define LINF 3e18+7#define MOD 1000000007using namespace std;typedef pair<int, int> P;typedef pair<ll, ll> LP;typedef pair<int, P> PP;typedef pair<ll, LP> LPP;typedef vector<unsigned int>vec;typedef vector<vec> mat;template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};const double PI = acos(-1.0);const double EPS = 1e-10;template<unsigned mod>struct RollingHash {unsigned base1;vector<unsigned> hash1;vector<unsigned> pow1;void init(const string &s) {int n = s.size();hash1.assign(n+1,0);pow1.assign(n+1,1);for(int i=0;i<n;i++) {hash1[i+1] = (hash1[i]+s[i]) * base1;pow1[i+1] = pow1[i] * base1;}}//ハッシュの基数RollingHash() : base1(100000007){}//aはbに幾つ含まれているかint contain(string a, string b){int ret = 0;int aLen = a.length(), bLen = b.length();if(aLen > bLen) return false;//BのaLen乗を計算unsigned ll t = 1;REP(i,aLen) t *= base1;//aとbの最初のaLen文字に関するハッシュ値を計算unsigned ll aHash = 0, bHash = 0;REP(i,aLen) aHash = aHash * base1 + a[i];REP(i,aLen) bHash = bHash * base1 + b[i];//bの場所を1つずつ進めながらハッシュ値をチェックfor(int i=0;i+aLen<=bLen;i++){if(aHash == bHash) ret++;//bのi文字目からのaLen文字が一致if(i + aLen < bLen) bHash = bHash * base1 + b[i+aLen] - b[i] * t;}return ret;}unsigned get(int l,int r) {unsigned t1 = ((hash1[r] - hash1[l] * pow1[r-l]) % mod + mod) % mod;return t1;}//ハッシュ値h1と長さh2Lenのハッシュ値h2を結合//動作未確認unsigned connect(unsigned h1, int h2, int h2Len) const {unsigned ret = ((h1 * pow1[h2Len] + h2) % mod + mod) % mod;return ret;}//区間[l1,r1)とハッシュテーブルがbからなる区間[l2,r2)の文字列の最長共通接頭辞の長さを求める//動作未確認int LCP(const RollingHash<mod> &b, int l1, int r1, int l2, int r2){int len = min(r1 - l1, r2 - l2);int low = -1;int high = len + 1;while(high - low > 1){int mid = (low + high) / 2;if(get(l1, l1 + mid) == b.get(l2, l2 + mid)) low = mid;else high = mid;}return low;}};int main(){cin.tie(0);ios::sync_with_stdio(false);string S;int M;cin >> S >> M;RollingHash<MOD> rh;rh.init(S);ll ans = 0;REP(i,M){string c;cin >> c;ans += rh.contain(c,S);}cout << ans << endl;}