Entries

スポンサーサイト (この記事を編集する[管理者用])

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

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2343-18c214cd
この記事にトラックバックする(FC2ブログユーザー)

UVa 12494 - Distinct Substring (この記事を編集する[管理者用])

Source

Another Bangladeshi Contest (2012-10-07)
UVa 12494

問題概要

アルファベット小文字から成る文字列Sが与えられる.Sの長さは200以下.
その部分文字列で,「異なる」ものが何個存在するかを求める問題.
異なるとは,頭から何文字をそのまま最後にくっつけたりして一致しないこと.

解法

部分文字列のハッシュ値を全部計算して調べた.
回転の任意性は,全回転のハッシュ値を計算して最小値を採用した.
ローリングハッシュを使えば,全回転のハッシュ値をO(計算したい文字列の長さ)で計算できる.
全部でO(|S|^3).

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2343-18c214cd
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。