結果

問題 No.430 文字列検索
ユーザー HIcoderHIcoder
提出日時 2024-08-25 00:27:16
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 6,621 bytes
コンパイル時間 1,206 ms
コンパイル使用メモリ 123,200 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-10 01:13:03
合計ジャッジ時間 18,551 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include<iostream>
#include<string>
#include<queue>
#include<vector>
#include<cassert>
#include<random>
#include<set>
#include<map>
#include<cassert>
#include<unordered_map>
#include<bitset>
#include<numeric>
#include<algorithm>
using namespace std;
typedef long long ll;
const int inf=1<<30;
const ll INF=1LL<<62;
typedef pair<int,ll> P;
typedef pair<int,P> PP; 
const ll MOD=998244353;

// SA-IS (O(N))
template<class Str> struct SuffixArray {
    // data
    Str str;
    //sa[0]は空文字になっていることに注意
    vector<int> sa, rsa, lcp;//勝手に代入される
    int& operator [] (int i) {
        return sa[i];
    }

    // constructor
    SuffixArray(const Str& str_) : str(str_) {
        build_sa();
    }
    void init(const Str& str_) {
        str = str_;
        build_sa();
    }
    void build_sa() {
        int N = (int)str.size();
        vector<int> s;
        for (int i = 0; i < N; ++i) s.push_back(str[i] + 1);
        s.push_back(0);
        sa = sa_is(s);
        rsa.assign(N + 1, 0);
        for (int i = 0; i <= N; ++i) rsa[sa[i]] = i;
        calc_lcp(s);
    }

    // SA-IS
    // upper: # of characters 
    vector<int> sa_is(vector<int> &s, int upper = 256) {
        int N = (int)s.size();
        if (N == 0) return {};
        else if (N == 1) return {0};
        else if (N == 2) {
            if (s[0] < s[1]) return {0, 1};
            else return {1, 0};
        }

        vector<int> isa(N);
        vector<bool> ls(N, false);
        for (int i = N - 2; i >= 0; --i) {
            ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);
        }
        vector<int> sum_l(upper + 1, 0), sum_s(upper + 1, 0);
        for (int i = 0; i < N; ++i) {
            if (!ls[i]) ++sum_s[s[i]];
            else ++sum_l[s[i] + 1];
        }
        for (int i = 0; i <= upper; ++i) {
            sum_s[i] += sum_l[i];
            if (i < upper) sum_l[i + 1] += sum_s[i];
        }

        auto induce = [&](const vector<int> &lms) -> void {
            fill(isa.begin(), isa.end(), -1);
            vector<int> buf(upper + 1);
            copy(sum_s.begin(), sum_s.end(), buf.begin());
            for (auto d: lms) {
                if (d == N) continue;
                isa[buf[s[d]]++] = d;
            }
            copy(sum_l.begin(), sum_l.end(), buf.begin());
            isa[buf[s[N - 1]]++] = N - 1;
            for (int i = 0; i < N; ++i) {
                int v = isa[i];
                if (v >= 1 && !ls[v - 1]) {
                    isa[buf[s[v - 1]]++] = v - 1;
                }
            }
            copy(sum_l.begin(), sum_l.end(), buf.begin());
            for (int i = N - 1; i >= 0; --i) {
                int v = isa[i];
                if (v >= 1 && ls[v - 1]) {
                    isa[--buf[s[v - 1] + 1]] = v - 1;
                }
            }
        };
            
        vector<int> lms, lms_map(N + 1, -1);
        int M = 0;
        for (int i = 1; i < N; ++i) {
            if (!ls[i - 1] && ls[i]) {
                lms_map[i] = M++;
            }
        }
        lms.reserve(M);
        for (int i = 1; i < N; ++i) {
            if (!ls[i - 1] && ls[i]) {
                lms.push_back(i);
            }
        }
        induce(lms);

        if (M) {
            vector<int> lms2;
            lms2.reserve(isa.size());
            for (auto v: isa) {
                if (lms_map[v] != -1) lms2.push_back(v);
            }
            int rec_upper = 0;
            vector<int> rec_s(M);
            rec_s[lms_map[lms2[0]]] = 0;
            for (int i = 1; i < M; ++i) {
                int l = lms2[i - 1], r = lms2[i];
                int nl = (lms_map[l] + 1 < M) ? lms[lms_map[l] + 1] : N;
                int nr = (lms_map[r] + 1 < M) ? lms[lms_map[r] + 1] : N;
                bool same = true;
                if (nl - l != nr - r) same = false;
                else {
                    while (l < nl) {
                        if (s[l] != s[r]) break;
                        ++l, ++r;
                    }
                    if (l == N || s[l] != s[r]) same = false;
                }
                if (!same) ++rec_upper;
                rec_s[lms_map[lms2[i]]] = rec_upper;
            }
            auto rec_sa = sa_is(rec_s, rec_upper);

            vector<int> sorted_lms(M);
            for (int i = 0; i < M; ++i) {
                sorted_lms[i] = lms[rec_sa[i]];
            }
            induce(sorted_lms);
        }
        return isa;
    }

    // prepair lcp
    vector<int> calc_lcp(const vector<int> &s) {
        int N = (int)s.size();
        lcp.assign(N - 1, 0);
        int h = 0;
        for (int i = 0; i < N - 1; ++i) {
            int pi = sa[rsa[i] - 1];
            if (h > 0) --h;
            for (; pi + h < N && i + h < N; ++h) {
                if (s[pi + h] != s[i + h]) break;
            }
            lcp[rsa[i] - 1] = h;
        }
        return lcp;
    }
};


struct z_algorithm{

    std::string s;
    int len;
    std::vector<int> z_array;
    bool is_build;
    z_algorithm(const std::string& s_):s(s_),len(s_.size()),is_build(false){
        z_array=std::vector<int>(len);
        build();
    }

    ~z_algorithm(){
        std::vector<int>().swap(z_array);
    }

    
    void build(){
        is_build = true;
        z_array[0]=len;
        int i=1;
        int j=0;
        while(i<len){
            while(i+j<len && s[i+j]==s[j])j++;

            //一致しなくなる or それ以上伸ばせない場合
            z_array[i]=j;

            if(j==0){
                i++;
                continue;
            }

            //j>0

            int k=1;
            while(k<j && k+z_array[k]<j){
                z_array[i+k]=z_array[k];
                k++;
            }
            i+=k;
            j-=k;
            
        }
    }   
    
    int operator[](int idx){
        assert(0<=idx && idx<len);
        if(!is_build) build();

        return z_array[idx];
    }


    void print(){
        for(int i=0;i<len;i++){
            std::cout<<"z_array["<<i<<"]="<<z_array[i]<<std::endl;
        }
        
    }
    
};


int main(){
    string S;
    cin>>S;
    int M;
    cin>>M;
    vector<string> C(M);
    for(int i=0;i<M;i++){
        cin>>C[i];
    }
    
    ll ans=0;
    for(int i=0;i<M;i++){
        string tmp=C[i]+'$'+S;

        z_algorithm za(tmp);
        int len=C[i].size();

        int cnt=0;
        for(int j=len+1;j+len<=tmp.size();j++){
            if(za[j]>=len){
                cnt++;
            }
        }
        //cout<<"i="<<i<<",cnt="<<cnt<<endl;
        ans+=cnt;
    }
    
    cout<<ans<<endl;
    
}
0