Z algorithm
コードについての説明
文字列 $S$ が与えられたとき $0 \le i < |S|$ について $S$ と $S[i:]$ の最長共通接頭辞の長さを求める線形時間アルゴリズム(参考).
(注) 以下の説明より (参考) の記事を見たほうがわかりやすい.
各ループの初めにおいて $i$ は今 $S$ と $S[i:]$ の最長共通接頭辞を求めていることを意味しており, また $j$ は $S$ と $S[i:]$ のうち先頭 $j$ 文字についてはすでに一致が確定していることを表す.
$1$ つ目の while 文では愚直に $S$ と $S[i:]$ の最長共通接頭辞を、確定していない $j + 1$ 番目以降の文字について愚直に一致を調べることで求めている. しかしこれだけでは線形にならない.
ここで $k(\ge 1)$ について $S$ と $S[i+k:]$ の最長共通接頭辞は $S$ と $S[i:]$ の先頭 $j$ 文字が一致することから $S$ と $S[k:]$ の最長共通接頭辞と一致することを用いる.
ただしこれは $k + $ ($S$ と $S[k:]$ の最長共通接頭辞の長さ) $ < j$ の場合の話である. 最後に重要なこととして $k$ がそのような条件を満たさなくなった場合でも
$S$ と $S[i + k:]$ の先頭 $j - k$ 文字は一致することが確定するのでループの最後において $j$ を $j - k$ に更新する.
最後に計算量を考える. まず $1$ つ目の while ループは $i + j$ の値に注目することで bound できる. $i + j$ は 1 つ目のループを回るごとに $1$ 増え, $2$ つ目のループでは変化しない. $i + j$ は $|S|$ 以下なので $1$ つ目の while ループを回る回数は高々 $|S|$ 回.
$2$ つ目の while ループは $i$ の値に注目することで bound できる. $i$ は $1$ つ目のループでは変化せず $2$ つ目の while ループでは回るごとに $1$ 増える. $i$ は $|S|$ 以下なので $2$ つ目の while ループを回る回数は高々 $|S|$ 回. よって合わせて $\O (|S|)$ となる.
時間計算量: $\O (|S|)$
時間計算量(オンライン版): add ならし $\O (1)$ query $\O(1)$
コード
void z_algorithm(const string& S, vector<int>& res)
{
int sz = (int)S.size();
res.resize(sz, sz);
int i = 1, j = 0;
while(i < sz){
while(i+j < sz && S[j] == S[i+j]) j++;
res[i] = j;
if(j == 0){
i++;
continue;
}
int k = 1;
while(i+k < sz && k+res[k] < j){
res[i+k] = res[k], k++;
}
i += k; j -= k;
}
}
コード(オンライン版)
class OnlineZalgo {
private:
string s;
vector<int> arr;
queue<int> unconfirm;
vector<vector<int> > info;
public:
OnlineZalgo() : arr(1), info(1){}
void add(char c){
s.push_back(c);
if((int)s.size() == 1) return;
info.push_back(vector<int>());
int nx = -1;
while(!unconfirm.empty()){
const int id = unconfirm.front();
if(arr[id] >= 0){
unconfirm.pop();
}else if(s[(int)s.size() - 1 - id] != c){
unconfirm.pop();
arr[id] += (int)s.size() - 1;
info.back().push_back(id);
}else{
nx = (int)s.size() - 1 - id;
break;
}
}
if(nx >= 0){
for(const auto& e : info[nx]){
const int id = (int)s.size() - 1 - nx + e;
arr[id] += (int)s.size() - 1;
info.back().push_back(id);
}
}
arr.push_back(0);
if(s[0] == c){
unconfirm.push((int)s.size() - 1);
arr.back() = -(int)s.size() + 1;
}
}
// s と s[index:] の最長共通接頭辞の長さを返す
int query(int index){
assert(index < (int)s.size());
if(index == 0) return (int)s.size();
return (arr[index] >= 0) ? arr[index] : (arr[index] + (int)s.size());
}
};
verify 用の問題
Atcoder : Prefix Suffix Free 提出コード