結果
| 問題 |
No.430 文字列検索
|
| コンテスト | |
| ユーザー |
_3_72_
|
| 提出日時 | 2019-09-24 18:29:56 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 800 ms / 2,000 ms |
| コード長 | 1,698 bytes |
| コンパイル時間 | 1,537 ms |
| コンパイル使用メモリ | 173,508 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-11-10 00:34:43 |
| 合計ジャッジ時間 | 9,894 ms |
|
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 14 |
ソースコード
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++)
#define REP(i,n) for(int i = 0;i < (n) ; i++)
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
//----------------------------------------------------------------
int MOD = 998244353;
// int MOD = 1000000007;
vll table[11];
//----------------------------------------------------------------
signed main(){
string s;
ll m;
cin >> s >> m;
vector<string> c(m);
rep(i,m)cin >> c[i];
ll cnt = 0;
ll base1 = 29;
ll M = 1000000007;
vll pow(s.size()+1);
pow[0] = 1;
vll hash1(s.size()+1,0);
rep(i,s.size()){
hash1[i+1] = (base1*hash1[i]%M + (s[i]-'A')+M)%M;
pow[i+1] = pow[i]*base1%M;
}
rep(i,m){
ll n = c[i].size();
ll h2 = c[i][0]-'A';
rep(k,n-1) h2 = (h2*base1%M + c[i][k+1]-'A'+M)%M;
for(int j = 0;j+n <= s.size();j++){
ll h1 = (hash1[j+n]-hash1[j]*pow[n]%M+M)%M;
if(h1 == h2)cnt++;
}
}
cout << cnt << endl;
return 0;
}
//----------------------------------------------------------------
// g++ -std=c++14 code1.cpp
// sudo pip3 install --upgrade online-judge-tools
// rm -r -f test;oj dl https://code-festival-2018-quala.contest.atcoder.jp/tasks/code_festival_2018_quala_c
// rm -r -f test;oj dl https://ddcc2017-final.contest.atcoder.jp/tasks/ddcc2017_final_b
// rm -r -f test;oj dl https://agc038.contest.atcoder.jp/tasks/agc038_a
_3_72_