結果

問題 No.430 文字列検索
ユーザー HIcoder
提出日時 2024-08-25 12:24:25
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 188 ms / 2,000 ms
コード長 10,103 bytes
コンパイル時間 1,247 ms
コンパイル使用メモリ 133,040 KB
最終ジャッジ日時 2025-02-24 00:43:22
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

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;
        }
        
    }
    
};
struct Trie{
    struct Node{
        std::map<char,int> to;
        int cnt;
        bool is_end;
        Node():cnt(0),is_end(false){}
    };
    vector<Node> nodes;
    Trie():nodes(1){}
    void insert(const string &s){
        int now=0;
        for(char c:s){
            if(!nodes[now].to.count(c)){
                nodes[now].to[c]=nodes.size();
                nodes.emplace_back(Node());
            }
            now=nodes[now].to[c];
        }
        nodes[now].cnt++;
        nodes[now].is_end=true;
    }
    ll ans=0;
    int dfs(int v){
        int res=nodes[v].cnt;
        for(auto [c,nv]:nodes[v].to){
            res+=dfs(nv);
        }
        if(v>0)ans+=res*(res-1)/2;
        return res;
    }
};
class RollingHash{
    long long  gcd(long long  x,long long  y){
        return y?gcd(y,x%y):x;
    }
    public:
        
        std::vector<long long> h; 
        std::vector<long long> powBase;
        int len;
        std::string str;
        long long mod;
        long long base;
        //RollingHash(const std::string& str,long long  base_=1000000+7,long long  mod_=1000000000+7):base(base_),mod(mod_){
        RollingHash(const std::string& str,long long  base_=1000000+7,long long  mod_=998244353):base(base_),mod(mod_){
            len=str.size();
            h = std::vector<long long>(len+1,0);
            powBase = std::vector<long long>(len+1,0);
            assert(gcd(base_,mod_)==1);
            h[0]=0;
            for(int i=1;i<=len;i++){
                h[i]=(h[i-1]*base%mod + (int)str[i-1])%mod; 
            }
            powBase[0]=1;
            for(int i=1;i<=len;i++){
                powBase[i]=powBase[i-1]*base%mod;
            }
        }
        ~RollingHash(){
            std::vector<long long>().swap(h);
            std::vector<long long>().swap(powBase);
        }
        //[0,idx]のハッシュ値を取得
        long long  get_hash(int idx){
            assert(0<=idx && idx<len);
            return h[idx+1];
        }
        long long pow(int i){
            assert(0<=i && i<=len);
            return powBase[i];
        }
        //0-indexed [l,r)のハッシュを取り出す
        long long  get_hash(int l,int r){
            assert(0<=l && r<=len);
            assert(l<r);
            int len=r-l;//[l,r)
            //h[r]-h[l]
            return (h[r] - (powBase[len]*h[l])%mod + mod)%mod;
        }
        long long getBase()const{
            return base;
        }
        long long getMod()const{
            return mod;
        }
        std::string getString()const{
            return str;
        }
        //[l,r)にしたい
        std::string getSubString(int l,int r)const{
            int len=r-l;
            return str.substr(l,len);
        }
        //[lからlen文字
        std::string getSubString(int l,unsigned int len)const{
            return str.substr(l,len);
        }
};
int main(){
    string S;
    cin>>S;
    // map<string,int> mp;
    // for(int i=0;i<S.size();i++){
    //     for(int j=1;j+i<=min(static_cast<int>(S.size()),10);j++){
    //         mp[S.substr(i,j)]++;
    //     }
    // }   
    int M;
    cin>>M;
    vector<string> C(M);
    for(int i=0;i<M;i++){
        cin>>C[i];
    }
    
    ll ans=0;
    /*
    //zアルゴリズムは厳しい
    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++;
            }
        }
        ans+=cnt;
    }
    cout<<ans<<endl;
    */
    RollingHash rh(S);
    vector<map<ll,ll>> mp(11);
    for(int x=1;x<=10;x++){
        for(int i=0;i+x<=S.size();i++){
            ll hash=rh.get_hash(i,i+x);
            mp[x][hash]++;
        }
    }
    
    for(int i=0;i<M;i++){
        RollingHash rh2(C[i]);
        ans+=mp[C[i].size()][rh2.get_hash(0,C[i].size())];
    }
    cout<<ans<<endl;
    
    
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0