README.md

character_strings

library for strings

Burrows Wheeler Transformation

burrows_wheeler.hpp
各文字を接尾辞でsort

• bwt_sa (construct from suffix array)
• inverse_bwt (restore string)
• construct directly (TODO)

Rolling Hash

rolling_hash.hpp
ハッシュを用いた文字列検索アルゴリズム

• RollingHash
  verify: AOJ(String Search)

Utils for String

string_utils.hpp
固定長のランダムな文字列を生成する

• generate_random_string

Suffix Array

suffix_array.hpp
接尾辞配列の構築

• Manber Myers
• SA-IS (TODO)

Text Search

text_search.hpp
文字列検索

• find_text (brute force)
  verify: AOJ(Naive String Search)
• kmp_search (KMP)
  verify: AOJ(Naive String Search)
• bm_search (BM)
  verify: AOJ(Naive String Search)
• sa_search (suffix array)
  verify: AOJ(Naive String Search)
• rh_search (rolling hash)
  verify: AOJ(String Search)
• z_search (Z algorithm)
  verify: AOJ(String Search)

Trie

trie.hpp
文字列を格納しておくための木

• trie

Z-Algorithm

z.hpp
文字列sとs[i:]の共通接頭辞の長さを線形時間で求める.
verify: Atcoder(ABCAC)

function	arguments	return	description	complexity
zarray	const string &s	vector<int> z	$z[i]=s[i:]$と$s[0:]$の共通接頭辞の長さ	$O(n)$

convert

convert.hpp
charとintを相互変換する

function	arguments	return	description	complexity
ato_int	char	int	小文字a-z $\to$ intへの変換	$O(1)$
to_achar	int	char	int $\to$ 小文字a-zへの変換	$O(1)$
Ato_int	char	int	A-Za-z $\to$ intへの変換(大文字は+26)	$O(1)$
to_Achar	int	char	int $\to$ A-Za-zへの変換(大文字は+26)	$O(1)$
dto_int	char	int	char0-9 $\to$ int0-9への変換(大文字は+26)	$O(1)$
to_dchar	int	char	int0-9 $\to$ char0-9への変換(大文字は+26)	$O(1)$

Palindromic Tree

palindromic_tree.hpp 回文に対するデータ構造

• Palindromic Tree (i番目の文字が最後の最長回文など.)
  verify: yukicoder(Common Palindromes Extra)