Skip to content

String

Jump to bottom
hotman edited this page Oct 25, 2020 · 3 revisions

アホコラ

#pragma once
#include<string>
#include<queue>

/**
 * @brief Aho-Corasick法
 */

class AhoCorasick{
    struct node;
    using np=node*;
    constexpr static int num=26;
    constexpr static char base='A';
    struct node{
        np ch[num];
        np link=nullptr;
        int val=0;
        node(){
            for(int i=0;i<num;++i)ch[i]=nullptr;
        }
    };
    np root=new node();
    np root_par=new node();
    public:
    AhoCorasick(){
        root->link=root_par;
        for(int i=0;i<num;++i)root_par->ch[i]=root;
    }
    void insert(std::string v){
        np t=root;
        int idx=0;
        while(idx<(int)v.size()){
            if(!t->ch[v[idx]-base])t->ch[v[idx]-base]=new node();
            t=t->ch[v[idx]-base];
            idx++;
        }
        t->val++;
    }
    void build(){
        built=1;
        std::queue<np>que;
        que.push(root);
        while(!que.empty()){
            np t=que.front();
            que.pop();
            for(int i=0;i<num;++i){
                if(!t->ch[i])continue;
                if(t==root){
                    t->ch[i]->link=t;
                }else{
                    np s=t->link;
                    while(!s->ch[i]){
                        s=s->link;
                    }
                    t->ch[i]->link=s->ch[i];
                }
                que.push(t->ch[i]);
            }
        }
    }
    bool built=0;
    int count(std::string v){
        if(!built){build();built=1;}
        np t=root;
        int idx=0;
        int res=0;
        while(idx<(int)v.size()){
            while(!t->ch[v[idx]-base]){
                if(t==root){
                    idx++;
                    if(idx==(int)v.size())return res;
                }else{
                    t=t->link;
                }
            }
            t=t->ch[v[idx++]-base];
            auto s=t;
            while(s!=root){
                res+=s->val;
                s=s->link;
            }
        }
        return res;
    }
    int find_first(std::string v){
        if(!built){build();built=1;}
        np t=root;
        int idx=0;
        int res=0;
        while(idx<(int)v.size()){
            while(!t->ch[v[idx]-base]){
                if(t==root){
                    res++;
                    idx++;
                    if(idx==(int)v.size())return -1;
                }else{
                    res++;
                    t=t->link;
                }
            }
            t=t->ch[v[idx++]-base];
            if(t->val>0)return res;
        }
        return -1;
    }
};

Manacher

#pragma once
#include<string>
#include<vector>

/**
 * @brief Manacher
 */

std::vector<int> manacher(std::string S){
    int i = 0, j = 0;
    std::string s;
    for(int i=0;i<(int)S.size();i++){
        if(i)s+='$';
        s+=S[i];
    }
    int n=s.size();
    std::vector<int>res(n,0);
    while (i<n) {
        while(i-j>=0&&i+j<n&&s[i-j]==s[i+j])++j;
        res[i]=j;
        int k=1;
        while (i-k >= 0 && k+res[i-k]<j)res[i+k]=res[i-k],++k;
        i+=k;j-=k;
    }
    for(int i=0;i<n;++i){
        if(i%2)res[i]=res[i]/2;
        else res[i]=(res[i]+1)/2;
    }
    return res;
}

オンラインZアルゴリズム

#pragma once
#include<string>
#include<vector>
#include<set>

/**
 * @brief オンラインZアルゴリズム
 */

struct online_Zalgo{
    std::vector<int>z;
    std::set<int>memo;
    std::vector<std::vector<int>>hist;
    std::string s="";
    int sz=0;
    void add(char c){
        s+=c;
        memo.emplace(sz);
        z.push_back(-1);
        hist.push_back(std::vector<int>());
        sz++;
        int mx=-1;
        for(auto itr=next(memo.begin(),1);itr!=memo.end();){
            auto idx=*itr;
            if(s[sz-idx-1]!=s.back()){
                itr=memo.erase(itr);
                z[idx]=sz-idx-1;
                hist.back().push_back(idx);
            }else{
                mx=idx;
                break;
            }
        }
        if(mx==-1)return;
        for(auto e:hist[sz-1-mx]){
            memo.erase(mx+e);
            z[mx+e]=sz-(mx+e)-1;
            hist.back().push_back(mx+e);
        }
    }
    int operator[](int idx){
        if(memo.count(idx))return sz-idx;
        else return z[idx];
    }
};

ローリングハッシュ

#pragma once
#include<string>
#include<vector>
#include<set>
#include<tuple>

/**
 * @brief ローリングハッシュ
 */

struct rolling_hash{
    using u64=std::uint64_t;
    constexpr static u64 mod=(1ULL<<61)-1;
    constexpr static u64 base=10007;
    int sz;
    u64 hash;
    constexpr rolling_hash():sz(0),hash(0){}
    constexpr rolling_hash(char c):sz(1),hash(c){}
    rolling_hash(std::string s):sz(0),hash(0){
        for(auto c:s)(*this)+=c;
    }
    constexpr u64 pow(u64 s,int t){
        u64 ret=1;
        while(t){
            if(t&1)ret=mul(ret,s);
            s=mul(s,s);
            t/=2;
        }
        return ret;
    }
    constexpr u64 add(u64 s,u64 t)noexcept{
        s+=t;
        return s>=mod?s-mod:s;
    }
    constexpr u64 sub(u64 s,u64 t)noexcept{
        if(s<t)s+=mod;
        return s-t;
    }
    constexpr u64 mul(u64 a,u64 b)noexcept{
        u64 au=a>>31,ad=a&((1ULL<<31)-1);
        u64 bu=b>>31,bd=b&((1ULL<<31)-1);
        u64 mid=au*bd+ad*bu;
        u64 ret=(au*bu*2+ad*bd+(mid>>30)+((mid&((1ULL<<30)-1))<<31));
        ret=(ret>>61)+(ret&mod);
        return ret>=mod?ret-mod:ret;
    }
    constexpr rolling_hash operator+(rolling_hash s)const noexcept{return rolling_hash(*this)+=s;}
    constexpr bool operator==(rolling_hash s)noexcept{return hash==s.hash&&sz==s.sz;}
    constexpr bool operator<(rolling_hash s)const noexcept{return std::make_pair(hash,sz)<std::make_pair(s.hash,s.sz);}
    constexpr bool operator>(rolling_hash s)const noexcept{return std::make_pair(hash,sz)>std::make_pair(s.hash,s.sz);}
    constexpr bool operator<=(rolling_hash s)const noexcept{return std::make_pair(hash,sz)<=std::make_pair(s.hash,s.sz);}
    constexpr bool operator>=(rolling_hash s)const noexcept{return std::make_pair(hash,sz)>=std::make_pair(s.hash,s.sz);}
    constexpr rolling_hash operator+=(rolling_hash s)noexcept{
        (*this).hash=add((*this).hash*pow(base,s.sz),s.hash);
        (*this).sz+=s.sz;
        return *this;
    }
    constexpr int size(){return sz;}
};

部分列DP

#pragma once
#include<string>
#include<vector>
#include<set>
#include<tuple>

/**
 * @brief 部分列DP(WIP)
 */

struct subsequence{
    struct node;
    using np=node*;
    struct node{
        np ch[26]={};
        int idx;
        char c;
        node(int idx,char c):idx(idx),c(c){}
    };
    std::string s;int n;
    std::vector<std::vector<int>>m;
    std::vector<np>v;
    np root=0;
    subsequence(std::string s):s(s),n(s.size()),m(n+1,std::vector<int>(26,-1)),v(n+1){
        for(int i=n-1;i>=0;--i){
            m[i]=m[i+1];
            m[i][s[i]-'a']=i;
        }
        for(int i=0;i<n+1;++i)v[i]=new node(i,(i?s[i-1]:'#'));
        for(int i=0;i<n;++i){
            for(int j=0;j<26;++j){
                if(~m[i][j])v[i]->ch[j]=v[m[i][j]+1];
            }
        }
        root=v[0];
    }
    //ここから問題ごとに書く
    std::vector<long long>dp;
    void dp2(){
        dp.resize(n+1);
        for(int i=n;i>=0;--i){
            np t=v[i];
            dp[i]=;
            for(int j=0;j<26;++j){
                if(!t->ch[j])dp[i]=1;
                else dp[i]=min(dp[i],dp[t->ch[j]->idx]+1);
            }
        }
    }
    string ans;
    void dfs(np t){
        for(int i=0;i<26;i++){
            if(!t->ch[i]){
                if(t!=root)ans+=t->c;
                ans+=char(i+'a');
                return;
            }
            if(dp[t->ch[i]->idx]==dp[t->idx]-1){
                if(t!=root)ans+=t->c;
                dfs(t->ch[i]);
                return;
            }
        }
    }
    string solve(){
        dp2();
        dfs(root);
        return ans;
    }
};

SA

#pragma once
#include<string>
#include<vector>
#include<algorithm>
#include <numeric>
#include<cmath>

/**
 * @brief SuffixArray
 */

std::vector<int> suffix_array(std::string s){
    int n=s.size();
    std::vector<int> v1(n,-1),v2(n,-1);
    std::vector<int> rank(n,-1);
    std::iota(v1.begin(),v1.end(),0);
    std::iota(v2.begin(),v2.end(),0);
    std::sort(v1.begin(),v1.end(),[&](auto p,auto q){return s[p]<s[q];});
    int idx=0;
    for(int i=0;i<n;++i){
        rank[v1[i]]=idx;
        if(i<n-1&&s[v1[i]]!=s[v1[i+1]])idx++;
    }
    for(int i=0;i<(int)std::log2(n)+2;++i){
        const int h=1<<i;
        std::sort(v2.begin(),v2.end(),[&](auto p,auto q){
            return make_pair(rank[p],p+h<n?rank[p+h]:-1)<make_pair(rank[q],q+h<n?rank[q+h]:-1);
        });
        swap(v1,v2);
        idx=0;
        std::vector<int> tmp(n,-1);
        for(int j=0;j<n;++j){
            tmp[v1[j]]=idx;
            if(j<n-1&&std::make_pair(rank[v1[j]],v1[j]+h<n?rank[v1[j]+h]:-1)<std::make_pair(rank[v1[j+1]],v1[j+1]+h<n?rank[v1[j+1]+h]:-1))idx++;
        }
        std::swap(rank,tmp);
    }
    return v1;
}

Zアルゴリズム

#pragma once
#include<string>
#include<vector>
#include<algorithm>

/**
 * @brief Zアルゴリズム
 */

std::vector<int> Z_algorizm(const std::string& s){
    std::vector<int>res(s.size());
    res[0]=s.size();
    int i=1,j=0;
    while(i<(int)s.size()){
        while(i+j<(int)s.size()&&s[j]==s[i+j])++j;
        res[i]=j;
        if(j==0){++i;continue;}
        int k=1;
        while(i+k<(int)s.size()&&k+res[k]<j)res[i+k]=res[k],++k;
        i+=k;j-=k;
    }
    return res;
}
int find_first(const std::string& s,const std::string& t){
    auto d=Z_algorizm(s+"#"+t);
    auto itr=std::find(d.begin()+s.size(),d.end(),s.size());
    if(itr!=d.end())return itr-d.begin()-s.size();
    else return -1;
}
int count(const std::string& s,const std::string& t){
    auto d=Z_algorizm(s+"#"+t);
    return std::count(d.begin()+s.size(),d.end(),s.size());
}
Clone this wiki locally