参考
用途
ナイーブな文字列検索 O(m*n)
- 普通に文字列検索を実装すると、
- 文字列sから文字列tを探すとして
- sの長さsl
- tの長さtl
- sのindex=0から滑らせてtの長さ分一致をチェックするので、計算量はO(sl * tl)
- ナイーブな実装↓
vector<ll> naive_search(string s, string t){
vector<ll> index_list;
FOR(i, 0, s.size() - t.size() + 1){
bool is_same = true;
FOR(j, 0, t.size()){
if(s[i+j]!=t[j]){
is_same = false;
break;
}
}
if(is_same){
index_list.push_back(i);
}
}
return index_list;
}
ローリングハッシュを用いた文字列検索 O(m+n)
- 互いに素な定数 1<b<h を用意する
- 文字列 t のハッシュ値を以下で定義する
- sの先頭からtl分の部分文字列のハッシュを求める
- tのハッシュを求める
- ハッシュが一致すれば文字列も一致している
- 次はsの2文字目からtl分を使ってハッシュを求めたいが、これは先程求めたsの部分文字列のハッシュに少し足し引きすれば求まる
- 詳しくは蟻本(第二版 p332)を見てほしい。hを264とし、型をunsigned long longとすることでmodを省略している
検証コード
vector<ll> naive_search(string s, string t){
vector<ll> index_list;
FOR(i, 0, s.size() - t.size() + 1){
bool is_same = true;
FOR(j, 0, t.size()){
if(s[i+j]!=t[j]){
is_same = false;
break;
}
}
if(is_same){
index_list.push_back(i);
}
}
return index_list;
}
vector<ll> rolling_hash_search(string s, string t){
vector<ll> index_list;
ll SL = s.size();
ll TL = t.size();
ll b = 1e6 + 7;
ll h = 1e9 + 7;
ll a = 1;
FOR(i, 0, TL){
a *= b;
a %= h;
}
ll s_hash = 0;
FOR(i, 0, TL){
s_hash = s_hash * b + s[i];
s_hash %= h;
}
ll t_hash = 0;
FOR(i, 0, TL){
t_hash = t_hash * b + t[i];
t_hash %= h;
}
FOR(i, 0, SL - TL + 1){
if(s_hash==t_hash){
index_list.push_back(i);
}
if(i+TL<SL){
s_hash = s_hash * b - s[i] * a + s[i+TL];
s_hash %= h;
}
}
return index_list;
}
int main(){
string s = "unvhusmjlvieloveuybouqvnqjygutqlovedkfsdfgheaiuloveaeiuvaygayfg";
string t = "love";
auto A = naive_search(s, t);
vprint(A);
auto B = rolling_hash_search(s, t);
vprint(B);
return 0;
}
出力
12 31 47
12 31 47
注意点
衝突
ll b = 1e7 + 7;
ll h = 1e11 + 7;
h=264
![プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?](https://images-fe.ssl-images-amazon.com/images/I/41bHxtpurqL._SL160_.jpg "プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?")
