結果

問題 No.430 文字列検索
ユーザー petite_progpetite_prog
提出日時 2020-01-25 19:26:27
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 404 ms / 2,000 ms
コード長 3,583 bytes
コンパイル時間 1,631 ms
コンパイル使用メモリ 179,408 KB
実行使用メモリ 30,208 KB
最終ジャッジ日時 2024-11-10 00:40:31
合計ジャッジ時間 3,607 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 404 ms
30,208 KB
testcase_02 AC 12 ms
5,248 KB
testcase_03 AC 13 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 390 ms
29,824 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 18 ms
6,144 KB
testcase_11 AC 105 ms
10,752 KB
testcase_12 AC 107 ms
10,624 KB
testcase_13 AC 109 ms
10,752 KB
testcase_14 AC 79 ms
8,064 KB
testcase_15 AC 62 ms
6,528 KB
testcase_16 AC 19 ms
5,248 KB
testcase_17 AC 14 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
　　　∫ ∫ ∫
　　　ノヽ
　　（＿　 ）
　（＿　　　 ）
（＿＿＿＿＿＿ ）
　ヽ(´･ω･)ﾉ　
　　 |　 /
　　 UU
*/
#include <bits/stdc++.h>
typedef long long int64;
using namespace std;
using P = pair<int64, int64>;
typedef vector<int> vi;
const int MOD = (int)1e9 + 7;
const int64 INF = 1LL << 62;
const int inf = 1<<30;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define REP(i, n) for (int i = 0; i < (n); i++)
#define FOR(i,s,n) for (int i = s; i < (n); i++)
#define ALL(obj) (obj).begin(), (obj).end() //コンテナじゃないと使えない!!
#define debug(x) cerr << #x << ": " << x << "\n";
#define mp make_pair
template <typename T>
ostream& operator<<(ostream& os, vector<T> &V){
    int N = V.size();
    REP(i,N){
        os << V[i];
        if (i!=N-1) os << " ";
    }
    os << "\n";
    return os;
}
template <typename T,typename S>
ostream& operator<<(ostream& os, pair<T,S> const&P){
    os << "(";
    os << P.first;
    os << " ";
    os << P.second;
    os << ")";
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, set<T> &S){
    auto it=S.begin();
    while(it!=S.end()){
        os << *it;
        os << " ";
        it++;
    }
    os << "\n";
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, deque<T> &q){
    for(auto it=q.begin();it<q.end();it++){
        os<<*it;
        os<<" ";
    }
     os<<endl;
    return os;
}
vector<pair<int,int>> dxdy = {mp(0,1),mp(1,0),mp(-1,0),mp(0,-1)};
//fixed<<setprecision(10)<<ans<<endl;

random_device seed_gen; 
mt19937_64 engine(seed_gen());
const uint64_t random_base = engine()%100000+1000;
template <typename T> 
struct RollingHash{
    const uint64_t mod = (1ull << 61) - 1;
    const uint64_t base = random_base;
    const uint64_t MASK31 = (1ull << 31) - 1;
    const uint64_t MASK30 = (1ull << 30) - 1;
    vector<uint64_t> pows, hash;
    RollingHash(const T& S)
        : pows(S.size()+1,1), hash(S.size()+1,0) {
        size_t N = S.size();
        for(int i=0; i<N; i++){
            hash[i+1] = CalcMod( Mul(hash[i], base) + S[i] );
            pows[i+1] = CalcMod( Mul(pows[i], base));
        }
    }

    uint64_t Mul(uint64_t a, uint64_t b){
        uint64_t au = a>>31 , ad = a & MASK31; //上位30bitと下位31bit
        uint64_t bu = b>>31 , bd = b & MASK31; //上位30bitと下位31bit

        uint64_t mid = ad*bu + au*bd, midu = mid>>30, midd = mid&MASK30;
        return au*bu*2 + midu + (midd<<31) + ad*bd;
    }

    uint64_t CalcMod(uint64_t val){
        val = (val&mod) + (val>>61);
        if (val >= mod) val-=mod;
        return val;
    }

    uint64_t get_hash(int l, int r){
        if (r<l){
            cerr << "r<l:" << make_pair(l,r) << endl;
        }
        unsigned long long a = hash[r], b =CalcMod( Mul(hash[l] , pows[r-l]));
        while (a<b) a+= mod;
        uint64_t res = CalcMod(a-b);
        return res;
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    int N = S.size();

    RollingHash<string> RH(S);
    auto a = RH.get_hash(1,11);
    map<unsigned long long, int> cnt;
    REP(l,N){
        for(int r=l+1; r<=min(N,l+11); r++){
            cnt[RH.get_hash(l,r)]++;
        }
    }
    int M;
    cin >> M;

    int ans=0;
    REP(i,M){
        string s; cin >> s;
        RollingHash<string> rh(s);
        ans += cnt[rh.get_hash(0,s.size())];
    }


    cout << ans << endl;
}
0