この記事はポエムアドベントカレンダー4日目の記事です。

www.adventar.org

大量の文字列データを扱うことの多くなった現代において、文字列処理ライブラリの高速化は重要である。 しかしながら、個人レベルで汎用的かつ高速な文字列処理ライブラリを作成することは難しい。 今回は汎用性を少し下げることにより圧倒的な高速化をした文字列処理ライブラリ「A」を制作した。

ソースコード

gist.github.com

ライブラリの仕様

文字列の制約

• すべての文字がAで構成されていること

制約を満たす文字列の例

AAAAAA

AAAAAAAAAA

制約を満たさない文字列の例

aaa

ABCDE

制約を満たさない文字列を用いた場合、正しくない結果を得る可能性がある。

利用方法

ライブラリ中では専用の効率的なデータ構造により文字列を管理する。そのため、利用するにはstd::stringから変換処理を行う必要がある。

A a(std::string(100, 'A'));

専用のデータ構造からstd::stringに変換するにはto_cppstringメンバ関数を用いる。

実装されているアルゴリズム

検索 find(A_1, A_2)

文字列の部分文字列に正規表現に一致するものが存在すればその位置（複数あればそのうち最も先頭に近いもの）を返す。 計算量:

置換 replace(A_1, A_2, A_3)

文字列の部分文字列に正規表現に一致するものが存在すればそれをすべてで置き換える。 計算量:

編集距離 edit_distance(A_1, A_2)

2つの文字列の編集距離を計算する。 計算量:

最長共通部分列 longest_common_subsequence(A_1, A_2)

2つの文字列の共通部分列で最も長いものを返す。 計算量:

最長回文 longest_palindrome(A)

回文になっている部分文字列のうち最も長いものとその始点を返す。 計算量:

今後の課題

• さらなるライブラリの充実
• Bのみからなる文字列を高速に扱えるライブラリの開発