UVa 12974 - Exquisite Strings

Source

Regional WarmUp(20151024)
(Competitive Programming Network - Eleventh Activity - 2015, Premio Fase II México & Centroamérica The ACM-ICPC in ESCOM-IPN 2015)
UVa 12974

問題概要

$N$ 文字のアルファベット小文字のみからなる文字列 $S$ と正整数 $K$ が与えられる.
$S$ の部分文字列のペア(異なる $2$ つからなる組)で,最初の $K$ 文字以上が一致しているものは何個あるかを ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題.
部分文字列は,切り出す場所が違えば違うものとみなす.

解法

Suffix Arrayを構築し,隣同士のLongest Common Prefixの長さを保存する配列を作る.
部分文字列は最低でも $K$ 文字はなければならず,最初の $K$ 文字以外は条件をみたすかどうかは関係ない.
よって,各場所を始点に選び,$K$ 文字以上使う場合の数は簡単な数式で求める.
後は,LCPの長さが $K$ 以上の部分をグループにしてしまい,そのグループ内の部分文字列をペアにできるとして計算していけば良い.
Suffix Arrayの構築にSA-ISなどを用いれば,時間計算量 $O(N)$.

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります.


Current time: 2017年11月21日04時10分44秒
Last modified: 2015年11月02日15時27分09秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20151024_1
トップページに戻る

Logged in as: unknown user (not login)

ログイン: