2017-09

Latest Entries

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

POJ

POJ 3415: Common Substrings


文字列 A, B に対して,k >= K かつ A[i .. i + k] = B[j .. j + k] なる組 (i, j, k) の個数を求める.
1 <= K <= |A|, |B| <= 100,000,文字はアルファベット.

A ~ '!' ~ B の Suffix Array と高さ配列を構築.長さ k の部分文字列として共通なものは LCP の長さが k 以上で繋がっている各部分に対して,A 由来が a 個,B 由来が b 個であれば a * b 個カウントされる.k の降順に考えれば,Union-Find と同時に a, b も管理していくことができる.
Suffix Array の構築は O((|A| + |B|) (log (|A| + |B|))^2) を用いた.2.5 秒.
スタックを用いて O(|A| + |B|) でも解ける (たぶん).

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/41-5b462339

この記事にトラックバックする(FC2ブログユーザー)

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。