結果

問題 No.430 文字列検索
ユーザー planesplanes
提出日時 2022-11-19 12:24:55
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 70 ms / 2,000 ms
コード長 1,755 bytes
コンパイル時間 2,110 ms
コンパイル使用メモリ 184,636 KB
実行使用メモリ 6,268 KB
最終ジャッジ日時 2023-10-20 17:40:53
合計ジャッジ時間 3,708 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 70 ms
6,268 KB
testcase_02 AC 40 ms
6,180 KB
testcase_03 AC 41 ms
6,180 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 67 ms
6,020 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 7 ms
4,348 KB
testcase_11 AC 65 ms
6,180 KB
testcase_12 AC 65 ms
6,180 KB
testcase_13 AC 66 ms
6,180 KB
testcase_14 AC 63 ms
6,180 KB
testcase_15 AC 60 ms
6,180 KB
testcase_16 AC 44 ms
6,180 KB
testcase_17 AC 41 ms
6,180 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

  #include <bits/stdc++.h> 
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 #define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)


ll b1=10007;
ll b2=10009;



ll h1=1000000007;
ll h2=998244353;



struct rolling_hash {

vector<ll> hs1;
vector<ll> hs2;
vector<pair<ll,ll>> note;




rolling_hash(string &S,ll m){
  hs1=vector<ll> ((ll)S.size());
  hs2=vector<ll> ((ll)S.size());
note=vector<pair<ll,ll>> (0);


  ll powb1=1;
  ll powb2=1;

  for(ll i=0;i<m;i++) {
    powb1*=b1;
    powb1%=h1;
    powb2*=b2;
    powb2%=h2;

    }

    ll a=0;
    ll b=0;
    for(ll i=0;i<m;i++) {
      a=a*b1+S[i];
      b=b*b2+S[i];
      a%=h1;
      b%=h2;
    }

    if(a<0) a+=h1;
    if(b<0) b+=h2;


    hs1[0]=a;
    hs2[0]=b;
  
  note.push_back(make_pair(a,b));

  for(ll i=1;i+m-1<(ll)S.size();i++) {
    a=a*b1+S[i+m-1]-S[i-1]*powb1;
    a%=h1;
    b=b*b2+S[i+m-1]-S[i-1]*powb2;
    b%=h2;

if(a<0) a+=h1;
if(b<0) b+=h2;
    hs1[i]=a;
    hs2[i]=b;

    note.push_back(make_pair(hs1[i],hs2[i]));

  }

  sort(all(note));

}


};



int main() {



  string S;cin>>S;
  ll M;
  cin>>M;
vector<vector<string>> vec(10,vector<string> (0));


ll ans=0;

  for(ll i=0;i<M;i++) {
    string s;cin>>s;
   vec[(ll)s.size()-1].push_back(s);
   
  }




   

   for(ll i=0;i<min((ll)S.size(),10LL);i++) {
    rolling_hash p(S,i+1);

    for(auto x:vec[i]) {
      ll a=0;
      ll b=0;
      for(ll j=0;j<x.size();j++) {
        a=a*b1+x[j];
        b=b*b2+x[j];

        a%=h1;
        b%=h2;
      }

      if(a<0) a+=h1;
      if(b<0) b+=h2;

      



    ll k=lower_bound(all(p.note),make_pair(a,b+1))-lower_bound(all(p.note),make_pair(a,b));
    ans+=k;


    }

   }


   cout<<ans<<endl;
}
0