結果

問題 No.430 文字列検索
ユーザー KoshStormKoshStorm
提出日時 2018-09-24 23:04:35
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 74 ms / 2,000 ms
コード長 3,095 bytes
コンパイル時間 1,647 ms
コンパイル使用メモリ 169,228 KB
実行使用メモリ 45,848 KB
最終ジャッジ日時 2023-10-24 22:19:35
合計ジャッジ時間 3,106 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 74 ms
45,848 KB
testcase_02 AC 50 ms
14,328 KB
testcase_03 AC 50 ms
14,328 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 41 ms
4,348 KB
testcase_09 AC 3 ms
5,460 KB
testcase_10 AC 3 ms
4,348 KB
testcase_11 AC 68 ms
31,680 KB
testcase_12 AC 73 ms
36,628 KB
testcase_13 AC 74 ms
36,652 KB
testcase_14 AC 63 ms
27,952 KB
testcase_15 AC 56 ms
20,480 KB
testcase_16 AC 54 ms
20,480 KB
testcase_17 AC 54 ms
20,472 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define REP(i,n) for (long long i=0;i<(n);i++)
#define FOR(i,a,b) for (long long i=(a);i<(b);i++)
#define RREP(i,n) for(long long i=n;i>=0;i--)
#define RFOR(i,a,b) for(long long i=(a);i>(b);i--)
#define dump1d_arr(array) REP(i,array.size()) cerr << #array << "[" << (i) << "] ==> " << (array[i]) << endl
#define dump2d_arr(array) REP(i,array.size()) REP(j,array[i].size()) cerr << #array << "[" << (i) << "]" << "[" << (j) << "] ==> " << (array[i][j]) << endl
#define dump(x)  cerr << #x << " => " << (x) << endl
#define dumpP(p) cerr << "( " << p.first << " , " << p.second << " )" << ends
#define SORT(c) sort((c).begin(),(c).end())
#define MIN(vec) *min_element(vec.begin(), vec.end())
#define MAX(vec) *max_element(vec.begin(), vec.end())
#define UNIQ(vec) vec.erase(unique(vec.begin(), vec.end()),vec.end()) //ソートの必要あり
#define IN(n,m)  (!(m.find(n) == m.end()))
#define ENUM(m) for (auto itr = m.begin(); itr != m.end(); ++itr)
#define dump_MAP(m) for(auto itr = m.begin(); itr != m.end(); ++itr) { cerr << itr->first << " --> "  << itr->second << endl; }
#define FINDL(vec,x) (lower_bound(vec.begin(),vec.end(),x) - vec.begin())
#define FINDU(vec,x) (upper_bound(vec.begin(),vec.end(),x) - vec.begin())
#define ROUND(N) setprecision(N)
#define ROUND_PRINT(N,val) cout << fixed;cout << setprecision(N) << val << endl
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define INARR(h,w,x,y) (0 <= y && y < h && 0 <= x && x < w)
#define EQ(a,b) (abs(a - b) < 1e-10)
using namespace std;
constexpr int dx[4] = {0,1,0,-1};
constexpr int dy[4] = {1,0,-1,0};
constexpr long double pi = M_PI;
constexpr double EPS = 1e-10;
constexpr long MOD = 1000000007;
constexpr short shINF = 32767;
constexpr long loINF = 2147483647;
constexpr long long llINF = 9223372036854775807;
typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<LL,LL> pr;
typedef vector<bool> VB;
typedef vector<pr> VP;
typedef priority_queue<pr,vector<pr>,greater<pr>> pq;


struct Trie {
  bool leaf;
  Trie* node[256];
  Trie(){
    leaf = false;
    for(int i=0; i<256; i++){
      node[i] = (Trie*)0;
    }
  }
  void insert(const string &str){
    Trie *r = this;
    for(int i=0; i<str.length(); i++){
      char c = str[i];
      if(!r->node[c]) r->node[c] = new Trie;
      r = r->node[c];
    }
    r->leaf = true;
  }
  int find(const string &str) const {
    const Trie *r = this;
    int cnt = 0;
    for(int i=0; i<str.length(); i++){
      char c = str[i];
      if(!r->node[c]) return cnt;
      r = r->node[c];
      if ((r->leaf) == 1) {
        ++cnt;
      }
    }
    return cnt;
  }    
};



int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    long M;
    string S,C;
    cin >> S >> M;
    Trie tree;
    REP(i,M) {
        cin >> C;
        tree.insert(C);
    }
    string s = S;
    LL cnt = 0;
    while (s.size() > 0) {
        cnt += tree.find(s);
        s = s.substr(1);
    }
    cout << cnt << endl;
    
}
0