mmrz's library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by mm-rz Hosted on GitHub Pages — Theme by mattgraham

Suffix Array
(string/suffix_array.hpp)

• View this file on GitHub
• Last update: 2025-07-01 03:22:56+09:00
• Include: #include "string/suffix_array.hpp"

Suffix Array

使い方

配列で且つ、各項の比較が可能な型を T とする。 また、 T の長さを $N$ とする。

• suffix_array<T>(T S, gen_lcp) : S の Suffix Array を構築する $O(N \log^2 N)$
  • gen_lcp = true のとき : LCP 配列を構築する $O(N)$
• sa[i] : Suffix Array の $i$ 番目を返す。 $i$ は 1-indexed
• lcp[i] : LCP 配列の $i$ 番目を返す。 $i$ は 1-indexed

概要

Suffix Array は、接尾辞をソートしたもの。

LCP 配列（高さ配列）は、接尾辞配列における隣同士の接尾辞で、先頭何文字が共通しているかを表す配列。LCP は Longest Common Prefix の略。これを利用することで、 Number of Substrings 等の問題を解くことができる。

Suffix Array を計算するのにダブリングを用いている。SA-ISに変更することで、線形時間で構築可能となる。

（1-indexed と書いたのは、 $0$ 番目に空文字が入るためである）

参考

蟻本 p.335

Verified with

• verify/yosupo/number_of_substrings.test.cpp
• verify/yosupo/suffixarray.test.cpp

Code

#pragma once

#include<numeric>
#include<vector>

template <typename T> struct suffix_array {
	T s;
	std::vector<int> sa;
	std::vector<int> rank;
	std::vector<int> lcp;

	suffix_array(const T &str, bool gen_lcp = true) : s(str) {
		int n = (int)s.size();
		sa.resize(n+1);
		std::iota(sa.begin(), sa.end(), 0);
		rank.assign(n+1, -1);
		for(int i = 0;i < n;i++){
			rank[i] = s[i];
		}
		std::vector<int> tmp(n+1);
		int k;
		auto comp_sa = [&](int i, int j) -> bool {
			if(rank[i] != rank[j])return rank[i] < rank[j];
			int ri = i + k <= n ? rank[i+k] : -1;
			int rj = j + k <= n ? rank[j+k] : -1;
			return ri < rj;
		};
		for(k = 1;k <= n;k *= 2){
			sort(sa.begin(), sa.end(), comp_sa);
			tmp[sa[0]] = 0;
			for(int i = 1;i <= n;i++){
				tmp[sa[i]] = tmp[sa[i-1]] + (comp_sa(sa[i-1], sa[i]) ? 1 : 0);
			}
			rank = tmp;
		}

		if(not gen_lcp)return;

		lcp.assign(n, 0);
		int h = 0;
		for(int i = 0;i < n;i++){
			int j = sa[rank[i]-1];
			if(h)h--;
			for(;j+h < n and i+h < n;h++){
				if(s[j+h] != s[i+h])break;
			}
			lcp[rank[i]-1] = h;
		}
	}
};

#line 2 "string/suffix_array.hpp"

#include<numeric>
#include<vector>

template <typename T> struct suffix_array {
	T s;
	std::vector<int> sa;
	std::vector<int> rank;
	std::vector<int> lcp;

	suffix_array(const T &str, bool gen_lcp = true) : s(str) {
		int n = (int)s.size();
		sa.resize(n+1);
		std::iota(sa.begin(), sa.end(), 0);
		rank.assign(n+1, -1);
		for(int i = 0;i < n;i++){
			rank[i] = s[i];
		}
		std::vector<int> tmp(n+1);
		int k;
		auto comp_sa = [&](int i, int j) -> bool {
			if(rank[i] != rank[j])return rank[i] < rank[j];
			int ri = i + k <= n ? rank[i+k] : -1;
			int rj = j + k <= n ? rank[j+k] : -1;
			return ri < rj;
		};
		for(k = 1;k <= n;k *= 2){
			sort(sa.begin(), sa.end(), comp_sa);
			tmp[sa[0]] = 0;
			for(int i = 1;i <= n;i++){
				tmp[sa[i]] = tmp[sa[i-1]] + (comp_sa(sa[i-1], sa[i]) ? 1 : 0);
			}
			rank = tmp;
		}

		if(not gen_lcp)return;

		lcp.assign(n, 0);
		int h = 0;
		for(int i = 0;i < n;i++){
			int j = sa[rank[i]-1];
			if(h)h--;
			for(;j+h < n and i+h < n;h++){
				if(s[j+h] != s[i+h])break;
			}
			lcp[rank[i]-1] = h;
		}
	}
};

Back to top page