test/AOJ_2863.test.cpp

• View this file on GitHub
• Last update: 2023-07-16 21:56:51+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2863

Depends on

• String/RollingHash.hpp
• String/Trie.hpp
• template.hpp
• type/modint.hpp

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2863"

#include "../template.hpp"

#include "../type/modint.hpp"

#include "../String/Trie.hpp"

#include "../String/RollingHash.hpp"

using mint=ModInt<1000000007>;

const int sz=26;
int converter(char x){return x-'a';}

const int sq=(1<<9);


signed main(){
    int N;cin>>N;
    vector<string> S(N);
    cin>>S;
    string T;cin>>T;

    Trie<sz> trie(converter);
    vector<int> add_sz;

    ull base=RollingHash::generate_base();
    vector<ull> Sh;
    vector<int> Sh_sz;
    RollingHash Th(T, base);

    rep(i,N){
        if(S[i].size()>sq){
            RollingHash tmp(S[i], base);
            Sh.push_back(tmp.get(0,S[i].size()));
            Sh_sz.push_back(S[i].size());
        }else{
            trie.add(S[i]);
            add_sz.push_back(S[i].size());
        }
    }

    vector<mint> dp(T.size()+1, 0);
    dp[0]=1;

    rep(i,(int)T.size()){
        rep(j,(int)Sh.size()){
            if(i+Sh_sz[j]<=(int)T.size() and Th.get(i,i+Sh_sz[j])==Sh[j]){
                dp[i+Sh_sz[j]]+=dp[i];
            }
        }
        function<void(int)> f=[&](int k){
            dp[i+add_sz[k]]+=dp[i];
            return ;
        };
        trie.query(T,f,i);
    }
    cout<<dp.back()<<endl;
    return 0;
}

#line 1 "test/AOJ_2863.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2863"

#line 1 "template.hpp"
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) begin(x),end(x)
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 1000000007
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

struct IOSetup{
    IOSetup(){
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout<<fixed<<setprecision(12);
    }
} iosetup;
 
template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");
    return os;
}
template<typename T>
istream &operator>>(istream &is,vector<T>&v){
    for(T &x:v)is>>x;
    return is;
}

#line 4 "test/AOJ_2863.test.cpp"

#line 1 "type/modint.hpp"
template<int Mod>
struct ModInt{
    int x;
    ModInt():x(0){}
    ModInt(int y): x (y >= 0 ? y % Mod : (Mod - (-y) % Mod) % Mod){}
    ModInt(long long y){
        if (y >= 0)
        {
            x = (int)(y % (ll)(Mod));
        }
        else
        {
            int tmp = (int)((-y) % (ll)Mod);
            x = (Mod - tmp) % Mod;
        }
    }
    ModInt &operator+=(const ModInt &p){
        if((x += p.x) >= Mod) x -= Mod;
        return *this;
    }
    ModInt &operator-=(const ModInt &p){
        if((x += Mod - p.x) >= Mod) x -= Mod;
        return *this;
    }
    ModInt &operator*=(const ModInt &p){
        x = (int)(1ll * x * p.x % Mod);
        return *this;
    }
    ModInt &operator/=(const ModInt &p){
        (*this) *= p.inverse();
        return *this;
    }
    ModInt operator-()const{return ModInt(-x);}
    ModInt operator+(const ModInt &p)const{return ModInt(*this)+=p;}
    ModInt operator-(const ModInt &p)const{return ModInt(*this)-=p;}
    ModInt operator*(const ModInt &p)const{return ModInt(*this)*=p;}
    ModInt operator/(const ModInt &p)const{return ModInt(*this)/=p;}
    bool operator==(const ModInt &p)const{return x==p.x;}
    bool operator!=(const ModInt &p)const{return x!=p.x;}
    ModInt inverse()const{
        int a = x, b = Mod ,u = 1, v = 0, t;
        while(b>0){
            t=a/b;
            swap(a-=t*b,b);swap(u-=t*v,v);
        }
        return ModInt(u);
    }
    ModInt pow(long long n)const{
        ModInt ret(1),mul(x);
        while(n>0){
            if(n&1) ret*=mul;
            mul*=mul;n>>=1;
        }
        return ret;
    }
    friend ostream &operator<<(ostream &os,const ModInt &p){return os<<p.x;}
    friend istream &operator>>(istream &is,ModInt &a){long long t;is>>t;a=ModInt<Mod>(t);return (is);}
    static int get_mod(){return Mod;}
};
#line 6 "test/AOJ_2863.test.cpp"

#line 1 "String/Trie.hpp"
template<int sz>
struct Trie{
private:
    struct Node{
        int nxt[sz],cnt;
        vector<int> accept;
        Node():cnt(0){memset(nxt,-1,sizeof(nxt));}
    };

    function<int(char)> conv;
    vector<Node> nodes;
    int root;

    void add(const string &s,int id,int s_idx=0,int node_idx=0){
        if(s_idx==(int)s.size()){
            nodes[node_idx].accept.push_back(id);
            return ;
        }
        int k=conv(s[s_idx]);
        if(nodes[node_idx].nxt[k]==-1){
            nodes[node_idx].nxt[k]=(int)nodes.size();
            nodes.push_back(Node());
        }
        add(s,id,s_idx+1,nodes[node_idx].nxt[k]);
        nodes[node_idx].cnt++;
    }
    void query(const string &s,const function<void(int)> &f,int s_idx,int node_idx){
        for(auto &idx:nodes[node_idx].accept)f(idx);
        if(s_idx==(int)s.size()) return ;
        else {
            int k=conv(s[s_idx]);
            if(nodes[node_idx].nxt[k]==-1) return;
            query(s,f,s_idx+1,nodes[node_idx].nxt[k]);
        }
    }

public:
 
    Trie(function<int(char)> conv):conv(conv),root(0){nodes.push_back(Node());}
    void add(const string &s,int idx=-1){
        if(idx<0) idx=count();
        add(s,idx,0,0);
    }
    // f(k) := 文字列のidxを通過するのでそれに対する処理, s[s_idx]から読み始める
    void query(const string &s,const function<void(int)> &f,int s_idx=0){ query(s,f,s_idx,0); }

    bool search(const string &s){
        int node_idx=0;
        for(int i=0;i<(int)s.size();i++){
            int k=conv(s[i]);
            if(nodes[node_idx].nxt[k]==-1) return false;
            node_idx=nodes[node_idx].nxt[k];
        }
        return !nodes[node_idx].empty();
    }
    int count(){
        return nodes[0].cnt;
    }
    int size(){
        return (int)nodes.size();
    }
};
// // converter, lower_case alphabet -> int
// int conv(char x){return x-'a';}
#line 8 "test/AOJ_2863.test.cpp"

#line 1 "String/RollingHash.hpp"
// hash type
using ull=unsigned long long;
struct RollingHash{
    using ull=unsigned long long;
    using uint128=__uint128_t;
    static const ull MOD=(1ull<<61ull)-1;
    vector<ull>hashed,power;
    const ull base;
 
    static inline ull add(ull a,ull b){if((a+=b)>=MOD)a-=MOD;return a;}
    static inline ull mul(ull a,ull b){uint128 c=(uint128)a*b;return add(c>>61,c&MOD);}
    static inline ull generate_base(){
        mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
        uniform_int_distribution<ull>rand(1,RollingHash::MOD-1);
        return rand(mt);
    }
    RollingHash()=default;
    RollingHash(const string &s,ull base):base(base){
        int sz=(int)s.size();
        hashed.assign(sz+1,0);
        power.assign(sz+1,0);
        power[0]=1;
        for(int i=0;i<sz;i++){
            power[i+1]=mul(power[i],base);
            hashed[i+1]=add(mul(hashed[i],base),s[i]);
        }
    }
    template<typename T>
    RollingHash(const vector<T>&s,ull base):base(base){
        int sz=(int)s.size();
        hashed.assign(sz+1,0);
        power.assign(sz+1,0);
        power[0]=1;
        for(int i=0;i<sz;i++){
            power[i+1]=mul(power[i],base);
            hashed[i+1]=add(mul(hashed[i],base),s[i]);
        }
    }
    // hash[l,r)
    ull get(int l,int r)const{
        return add(hashed[r],MOD-mul(hashed[l],power[r-l]));
    }
    ull concat(ull hash1,ull hash2,int hash2len)const{
        return add(mul(hash1,power[hash2len]),hash2);
    }
    int lcp(const RollingHash &b,int l1,int r1,int l2,int r2)const{
        assert(b.base==base);
        int len=min(r1-l1,r2-l2);
        int lw=0,hi=len+1;
        while(hi-lw>1){
            int mid=(lw+hi)/2;
            if(get(l1,l1+mid)==b.get(l2,l2+mid))lw=mid;
            else hi=mid;
        }
        return lw;
    }
};
#line 10 "test/AOJ_2863.test.cpp"

using mint=ModInt<1000000007>;

const int sz=26;
int converter(char x){return x-'a';}

const int sq=(1<<9);


signed main(){
    int N;cin>>N;
    vector<string> S(N);
    cin>>S;
    string T;cin>>T;

    Trie<sz> trie(converter);
    vector<int> add_sz;

    ull base=RollingHash::generate_base();
    vector<ull> Sh;
    vector<int> Sh_sz;
    RollingHash Th(T, base);

    rep(i,N){
        if(S[i].size()>sq){
            RollingHash tmp(S[i], base);
            Sh.push_back(tmp.get(0,S[i].size()));
            Sh_sz.push_back(S[i].size());
        }else{
            trie.add(S[i]);
            add_sz.push_back(S[i].size());
        }
    }

    vector<mint> dp(T.size()+1, 0);
    dp[0]=1;

    rep(i,(int)T.size()){
        rep(j,(int)Sh.size()){
            if(i+Sh_sz[j]<=(int)T.size() and Th.get(i,i+Sh_sz[j])==Sh[j]){
                dp[i+Sh_sz[j]]+=dp[i];
            }
        }
        function<void(int)> f=[&](int k){
            dp[i+add_sz[k]]+=dp[i];
            return ;
        };
        trie.query(T,f,i);
    }
    cout<<dp.back()<<endl;
    return 0;
}

Back to top page