結果

問題 No.430 文字列検索
ユーザー WarToksWarToks
提出日時 2019-09-18 19:51:18
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 7,055 bytes
コンパイル時間 3,470 ms
コンパイル使用メモリ 149,728 KB
実行使用メモリ 25,124 KB
最終ジャッジ日時 2024-11-10 00:33:08
合計ジャッジ時間 7,635 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
10,496 KB
testcase_01 AC 747 ms
18,432 KB
testcase_02 TLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <array>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <chrono>
#include <random>
#include <math.h>

#define REP(i, n) for(int (i) = 0; (i) < (n); ++(i))


// RollingHashクラス
class RollingHash{
private:
    #define rep(i, n) for(int (i) = (0); (i) < (n); ++(i))
    using LLi = long long int;
    using V_LLi = std::vector<LLi>;
    // 32ビット以下の 素数
    static constexpr LLi One_E_Nine= 1e9;
    static constexpr int mod_size = 3;
    static std::array<LLi, mod_size> mod;
    static bool mod_not_chosen;

    static constexpr int base_size = 2;
    static constexpr std::array<LLi, base_size> base{9999991, 799976819}; // 原始元

    std::vector<std::vector<V_LLi>> power; // power[k][i][j] = (base[i])^k in mod[j]

    // ハッシュ値 | hash[range][i][j] : base[i], mod[j] 下での [0, range) の ハッシュ値
    std::vector<std::vector<V_LLi>> hash;
    
    // thePrimes[i] + 1e9 において, baseは原始元
    static constexpr int Arr_Size_thePrimes = 138;
    static constexpr std::array<int, Arr_Size_thePrimes> thePrimes{
        -9971, -9707, -9167, -9149, -8939, -8793, -8769, -8577, -8559, -8537, 
        -8531, -8331, -7901, -7463, -7421, -7361, -7241, -7217, -6917, -6363, 
        -6329, -6267, -6183, -6167, -6113, -6053, -5603, -5297, -5027, -4623,
        -4433, -4379, -4251, -4181, -4007, -3887, -3851, -3753, -3741, -3641,
        -3593, -3329, -3323, -3311, -2951, -2763, -2433, -2423, -2411, -2361,
        -2327, -2321, -1919, -1817, -1757, -1661, -1379, -1337, -1317, -1097,
        -869,  -807,  -647,  -609,  -497,  -413,  -117,  -107,     7,   411, 
        433,   637,   753,   871,  1099,  1329,  1447,  1449,  1621,  1647,
        1699,  1819,  1917,  1963,  2233,  2457,  3111,  3153,  3163,  3247,
        3373,  3513,  3679,  3747,  3777,  3889,  3919,  4249,  4263,  4627,
        4839,  5233,  5847,  5899,  5907,  6037,  6211,  6331,  6457,  6577,
        6607,  6621,  6697,  6751,  6961,  7117,  7243,  7257,  7279,  7383,
        7417,  7497,  8277,  8661,  8719,  8773,  9223,  9277,  9289,  9469,
        9519,  9541,  9573,  9667,  9679,  9757,  9859,  9867
    };

    const int n; // 入力文字列の大きさ
    std::string S; // 入力文字列
public:
    // コンストラクタ
    RollingHash(std::string &S_): n(S_.size()){
        S = S_; init();
    }
    // 初期化
    inline void init(){
        // modの選択 : まだ選ばれて居ない場合
        if(mod_not_chosen){
            std::random_device randRoll;
            std::vector<int> prev(mod_size, -1);
            
            auto fn_bad = [&](int idx, int ptr){
                for(int i = 0; i < idx; ++i) if(prev[i] == ptr) return true;
                mod[idx] = ptr; 
                return false;
            };
            
            rep(i, mod_size){
                int a; do{a = randRoll() % Arr_Size_thePrimes; }while(fn_bad(i, a));
                mod[i] = One_E_Nine - thePrimes[a];
            }
            
            mod_not_chosen = false;
        }

        // 大きさの確保
        power.resize(n+1, std::vector<V_LLi>(base_size, V_LLi(mod_size, 1)));
        hash.resize(n+1, std::vector<V_LLi>(base_size, V_LLi(mod_size, 0)));

        // 初期条件
        // power[0][0] = 1; power[0][1] = 1;
        // hash[0] = {{0, 0}, {0, 0}};

        // 実行
        rep(itr, n) rep(i, base_size) rep(j, mod_size){
                power[itr+1][i][j] = (power[itr][i][j] * base[i]) % mod[j];
                hash[itr+1][i][j]  = (hash[itr][i][j]  * base[i] + S[itr]) % mod[j];
        }
    }

    
    // ハッシュ値の取得 : [left, right) in 0-indexed
    inline LLi getHash(int left, int right, int b_id = 0, int m_id = 0){
        LLi res = hash[right][b_id][m_id] 
            - hash[left][b_id][m_id] * power[right-left][b_id][m_id] % mod[m_id];
        if(res < 0) res += mod[m_id];
        return res;
    }

    // s[start:] で lengthの長さのハッシュ値の取得 (0-indexed)
    inline LLi getHash_Length(int start, int length, int b_id = 0, int m_id = 0){
        return getHash(start, start+length, b_id, m_id);
    }

    // sa..., と sb... の長さLの文字列が等しいかをHashを用いて判定 : 0-indexed
    inline bool sameOf(int a, int b, int L){
        rep(i, base_size) rep(j, mod_size) if(getHash(a, a+L, i, j) != getHash(b, b + L, i, j)) return false;
        return true;
    }

    // 他の文字列のハッシュを用いて S[a:]とT[b:]の長さLの文字列の一致を判定
    inline bool sameOf(RollingHash &T, int a, int b, int L){
        rep(i, base_size) rep(j, mod_size)
            if(this->getHash_Length(a, L, i, j) != T.getHash_Length(b, L, i, j)) return false;
        return true;
    }

    // LCP of { S[a:] and S[b:] } in 0-indexed
    inline int getLCP(int a, int b){
        if(a > b) std::swap(a, b);
        int ok = 0, ng = n - b + 1;
        while(ng - ok > 1){
            int lngth = (ok + ng) / 2;
            if(sameOf(a, b, lngth)) ok = lngth;
            else ng = lngth;
        }
        return ok;
    }
    // 他の文字列のハッシュを用いて, S[a:] と T[b:]のLCPを取得
    inline int getLCP_with(RollingHash &T, int a, int b){
        int ok = 0, ng = std::min(T.n - b, this->n - a) + 1;
        while(ng - ok > 1){
            int mid = (ng + ok) >> 1;
            if(sameOf(T, a, b, mid)) ok = mid;
            else ng = mid;
        }
        return ok;
    }


    // ABC141 より : 長さ length の交わりの共通連続部分文字列の存在を判定 O(NlogN)
    inline bool findCP(int length){
        using pll = std::pair<LLi, LLi>;
        std::map<std::pair<pll, pll>, int> theHash;
        for(int x = 0; x + length <= n; x++){
            pll lp = {getHash_Length(x, length, 0, 0), getHash_Length(x, length, 0, 1)};
            pll rp = {getHash_Length(x, length, 1, 0), getHash_Length(x, length, 1, 1)};
            std::pair<pll, pll> P = {lp, rp};
            if(theHash.find(P) != theHash.end()) {
                if(x - theHash[P] >= length) return true;
            }
            else theHash[P] = x;
        }
        return false;
    }

    #undef rep
};  
// 静的メンバの初期化
bool RollingHash::mod_not_chosen = true;
std::array<RollingHash::LLi, RollingHash::mod_size> RollingHash::mod;

// ==================== ここまで ============================


constexpr int ALPHA = 'z' - 'a' + 1;
std::vector<int> indexes[ALPHA];
std::string S;


int main(void){
    std::cin >> S; const int L1 = S.size();
    REP(i, L1) indexes[S[i]-'A'].push_back(i);
    RollingHash SS(S);
    int m; std::cin >> m;
    int cnt = 0;
    while(m--){
        std::string T; std::cin >> T;
        RollingHash ST(T); const int L2 = T.size();
        int p = T.front() - 'A';
        for(int v : indexes[p]){
            if(v + L2 > L1) break;
            if(SS.sameOf(ST, v, 0, L2)) cnt++;
        }
    }

    std::cout << cnt << '\n';
    
    
    return 0;
}
0