Counting the Number of Distinct Substrings
コードについての説明
文字列 $s$ 内に含まれる相異なる(連続な)部分文字列の数を求めるアルゴリズム.
結論から述べると接尾辞配列 sa および隣接する接尾辞の最長共通接頭辞の長さを表す配列 lcp を構築することで可能になる.
これらの概念についてはある程度有名なのでここには書かない.
例えば $S =$ "abcbcba" とする. このとき $sa =$ {"a", "abcbcba", "ba", "bcba", "bcbcba", "cba", "cbcba"} となる.
接尾辞配列を前から見ていき, まず先頭の "a" を見て "a" を部分文字列として数え上げる. その次に "abcbcba" を見て "ab", "abc", "abcb", "abcbc", "abcbcb", "abcbcba" を数え上げる.
このとき部分文字列の数は ("abcbcba" の長さ) - ("a" と "abcbcba" の最長共通接頭辞) のようにして計算することができる. 言い換えると "ab" から始まる部分文字列を数え上げている.
同様に "ba" を見て "b", "ba" を数え上げる. 部分文字列の数は ("ba" の長さ) - ("abcbcba" と "ba" の最長共通接頭辞) に対応する. 言い換えると "b" から始まる部分文字列を数え上げている.
同様に "bcba" を見て "bc", "bcb", "bcba" を数え上げる. 部分文字列の数は ("bcba" の長さ) - ("ba" と "bcba" の最長共通接頭辞) に対応する. 言い換えると "bc" から始まる部分文字列を数え上げている.
これを繰り返して最終的に $22$ が答えとなる(空文字を部分文字列の $1$ つとして考えている).
以下の実装では接尾辞配列の構築に $\O (|S| \log^2 |S|)$ 時間かけているが SA_IS などの線形時間での接尾辞配列構築アルゴリズムを用いることで $\O (|S|)$ 時間で計算することが可能である.
時間計算量: $\O( |S| \log^2 |S|)$ (線形時間での接尾辞配列構築アルゴリズムを用いることで $\O (|S|)$ 時間に改善可能)
コード
class SuffixArray {
public:
int sz, index1, index2;
vector<int> rnk, tmp, sa, lcp;
SuffixArray(const string& arg)
: sz((int)arg.size()), rnk(sz+1), tmp(sz+1), sa(sz+1), lcp(sz+1){
make_sa(arg), make_lcp(arg);
}
void make_sa(const string& s){
index1 = sz;
for(int i = 0; i <= index1; ++i){
sa[i] = i;
rnk[i] = (i < index1) ? s[i] : -1;
}
auto comp = [&](const int i, const int j){
if(rnk[i] != rnk[j]){
return rnk[i] < rnk[j];
}else{
const int ri = (i + index2 <= index1) ? rnk[i + index2] : -1;
const int rj = (j + index2 <= index1) ? rnk[j + index2] : -1;
return ri < rj;
}
};
for(index2 = 1; index2 <= index1; index2 *= 2){
sort(sa.begin(), sa.end(), comp);
tmp[sa[0]] = 0;
for(int i = 1; i <= index1; ++i){
tmp[sa[i]] = tmp[sa[i-1]] + (comp(sa[i-1], sa[i]) ? 1 : 0);
}
for(int i = 0; i <= index1; ++i){
rnk[i] = tmp[i];
}
}
}
void make_lcp(const string& s){
for(int i = 0; i <= sz; ++i){
rnk[sa[i]] = i;
}
int h = 0;
lcp[0] = 0;
for(int i = 0; i < sz; ++i){
int j = sa[rnk[i]-1];
if(h > 0){
--h;
}
for(; j + h < sz && i + h < sz; ++h){
if(s[j+h] != s[i+h]){
break;
}
}
lcp[rnk[i]-1] = h;
}
}
};
long long solve(const string& s)
{
int n = (int)s.size();
long long ans = 1;
SuffixArray SA(s);
for(int i = 0; i < n; ++i){
ans += n - SA.sa[i+1] - SA.lcp[i];
}
return ans;
}
verify 用の問題
yosupo さんの library checker : Number of Substrings 提出コード