AtCoder が提供しているABC（AtCoder Beginner Contest）362 G問題をC++で解いてみました。ABC362は、2024年7月13日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
G問題 Count Substring Query（Difficulty : 1625）
問題の詳細は、リンク先をご覧ください。
ABC362 G問題 Count Substring Query
Suffix array を活用します。AtCoder Problems による Difficulty は 1625 でした。
解答案
与えられた文字列に対して、suffix array を構築すると、その文字列に特定の文字列が含まれているかを二分探索で高速に探すことができます。
Suffix array の解説は、別の記事にする予定です。
C++ プログラム例（ABC362G）
AtCoder Library が提供している suffix array を使います。関数 lower を使って、文字列 $T$ を含む suffix array のインデックスを二分探索で求めます。すべての英小文字より大きい文字コードを持つ ’~’ を加えて、文字列 $T$ を含む次のインデックスを求めます（35行目）。
以下が、C++プログラムです。
#include <bits/stdc++.h>
#include <atcoder/string>
using namespace std;
using namespace atcoder;
string s;
vector<int> sa;
int lower(string t)
{
int ng = -1;
int ok = s.size();
while (abs(ok - ng) > 1) {
int mid = (ok + ng) / 2;
if (s.substr(sa[mid], t.size()) >= t) {
ok = mid;
} else {
ng = mid;
}
}
return ok;
}
int main()
{
cin >> s;
sa = suffix_array(s);
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
string t;
cin >> t;
cout << lower(t + '~') - lower(t) << endl;
}
return 0;
}別解として、lower_bound と upper_bound に相当する関数を呼びます。関数 lower と関数 upper の差は、1行しかありません（15、31行目）。
関数 upper と lower の呼び出しの差が、該当している文字列の個数になります（51行目）。
#include <bits/stdc++.h>
#include <atcoder/string>
using namespace std;
using namespace atcoder;
string s;
vector<int> sa;
int lower(string t)
{
int ng = -1;
int ok = s.size();
while (abs(ok - ng) > 1) {
int mid = (ok + ng) / 2;
if (s.substr(sa[mid], t.size()) >= t) {
ok = mid;
} else {
ng = mid;
}
}
return ok;
}
int upper(string t)
{
int ng = -1;
int ok = s.size();
while (abs(ok - ng) > 1) {
int mid = (ok + ng) / 2;
if (s.substr(sa[mid], t.size()) > t) {
ok = mid;
} else {
ng = mid;
}
}
return ok;
}
int main()
{
cin >> s;
sa = suffix_array(s);
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
string t;
cin >> t;
cout << upper(t) - lower(t) << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
今回は、Python プログラムの紹介を省略します。
最後に
文字列検索で使われる suffix array について学ぶことができました。
引き続き ABC の問題を紹介していきます。
