結果

問題 No.430 文字列検索
ユーザー ate
提出日時 2020-08-11 13:16:30
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 86 ms / 2,000 ms
コード長 2,120 bytes
コンパイル時間 3,093 ms
コンパイル使用メモリ 232,572 KB
最終ジャッジ日時 2025-01-12 20:14:28
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>

using std::cout;
using std::endl;

struct trie{
  struct node{
    std::vector<int> next_alp;
    int val;
    node():next_alp(26,-1),val(-1){}
    node(int k):next_alp(26,-1),val(k){}
    node(int c,int id):next_alp(26,-1),val(-1){
      next_alp[c] = id;
    }
  };
  std::vector<node> nodes;
  int k;
  trie():nodes(26),k(0){}
  void dump(){
    for(int i=0;i<nodes.size();++i){
      auto& n = nodes[i];
      if(std::all_of(n.next_alp.begin(),n.next_alp.end(),[](int v){return v==-1;}))continue;
      cout<<i<<":"<<endl;
      for(auto x:n.next_alp)cout<<x<<" ";
      cout<<endl;
      cout<<n.val<<endl;
    }
    cout<<endl;
  }
  std::vector<int> encode(std::string const& s){
    int n = s.size();
    std::vector<int> a(n);
    for(int i=0;i<n;++i)a[i]=s[i]-'a';
    return a;
  }
  void add_impl(std::vector<int> const& a,int ai,int nodei){
    if(ai+1==a.size()){
      nodes[nodei].val = k++;
      return;
    }
    auto& nxt = nodes[nodei].next_alp[a[ai+1]];
    if(nxt==-1){
      nxt = nodes.size();
      nodes.emplace_back();
    }
    add_impl(a,ai+1,nxt);
  }
  void add(std::string const& s){
    add_impl(encode(s),0,s[0]-'a');
  }
  bool find(std::string const& s){
    auto cur = nodes[s[0]-'a'];
    for(int i=0;i+1<s.size();++i){
      int c = s[i+1]-'a';
      if(cur.next_alp[c]==-1)return false;
      cur = nodes[cur.next_alp[c]];
    }
    return true;
  }
  int get(std::string const& s){
    int res = 0;
    auto cur = nodes[s[0]-'a'];
    if(cur.val!=-1){
      res++;
    }
    for(int i=0;i+1<s.size();++i){
      int c = s[i+1]-'a';
      if(cur.next_alp[c]==-1)break;
      cur = nodes[cur.next_alp[c]];
      if(cur.val!=-1){
        res++;
      }
    }
    return res;
  }
};

signed main(){

  using namespace std;

  string s;
  cin>>s;
  int m;
  cin>>m;
  trie t;
  for(int i=0;i<m;++i){
    string c;
    cin>>c;
    for(auto& ci:c)ci=tolower(ci);
    t.add(c);
  }
  for(auto& si:s)si=tolower(si);
  int ans = 0;
  for(int i=0;i<s.size();++i){
    int tmp = t.get(s.substr(i));
    ans += tmp;
  }
  cout<< ans <<endl;

}
0