#include "string/rolling_hash.hpp"
#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;} };
#line 2 "string/rolling_hash.hpp" #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;} };