これは「データ構造とアルゴリズム Advent Calendar 2018」9日目の記事です. はじめに Suffix array1 はよく知られたデータ構造のひとつです.1990年に提案2されて以来,その使われ方は多岐にわたります.本記事では,この suffix array の基本事項として, suffix array とは何か suffix array を全文索引として用いる方法 を紹介したいと思います. パターンマッチングと全文索引 パターンマッチング とは,文字列 $T$ から,パターンと呼ばれる文字列 $P$ を探す問題です.たとえば, $T =$ 麒麟鼬蝙蝠駱駝蝦蟇鼈樹懶鼠膃肭臍羆狒狒鰐麒麟猩猩鼠鼠鼠鼠鼠蟒蛇鼈鼬羆蜥蜴駱駝羆麒麟鼈鼬狒狒狒狒羆蝙蝠膃肭臍麒麟蝙蝠鼬蜥蜴鼬狒狒蝮樹懶鼬羆蝮膃肭臍麒麟羆駱駝蝙蝠蟒蛇狒狒蝙蝠樹懶鼈蜥蜴駱駝羆鼬羆樹懶犀鰐蝙蝠鼠狒狒蝦蟇鼬蜥蜴鼠蝮蝦蟇蜥蜴龍麒
![Suffix Array - Qiita](https://cdn-ak-scissors.b.st-hatena.com/image/square/0d639322164121fef0446daa4385b9cf9e9c6430/height=288;version=1;width=512/https%3A%2F%2Fqiita-user-contents.imgix.net%2Fhttps%253A%252F%252Fcdn.qiita.com%252Fassets%252Fpublic%252Fadvent-calendar-ogp-background-7940cd1c8db80a7ec40711d90f43539e.jpg%3Fixlib%3Drb-4.0.0%26w%3D1200%26mark64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTk3MiZoPTM3OCZ0eHQ9U3VmZml4JTIwQXJyYXkmdHh0LWFsaWduPWxlZnQlMkN0b3AmdHh0LWNvbG9yPSUyMzNBM0MzQyZ0eHQtZm9udD1IaXJhZ2lubyUyMFNhbnMlMjBXNiZ0eHQtc2l6ZT01NiZzPWU5NmU0ZTM3NDZkZjM3N2ZkZmRlNzFkMWNhNGE0NTM0%26mark-x%3D120%26mark-y%3D96%26blend64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZoPTc2Jnc9OTcyJnR4dD0lNDBmbGFyZSZ0eHQtY29sb3I9JTIzM0EzQzNDJnR4dC1mb250PUhpcmFnaW5vJTIwU2FucyUyMFc2JnR4dC1zaXplPTM2JnR4dC1hbGlnbj1sZWZ0JTJDdG9wJnM9NGFjNDJkZmUxNmIyMjAxYmE4ZDUwZGU4YTRhZDE1ZDY%26blend-x%3D120%26blend-y%3D500%26blend-mode%3Dnormal%26s%3D4a4be3a18093a5dcc0847097ddfa74a7)