SPOJ 23507 - Retrovirus [RETRO]

Source

SPOJ 23507 [RETRO]

問題概要

文字列 $S$ に対して,$i$ 文字目から $j$ 文字目まででなる $S$ の部分文字列を $S[i,j]$ と書く.
また,同じ長さ $k$ の文字列 $S,T$ に対して,その類似度は $S[i,i]=T[i,i]$ を満たす $i=1,2,\ldots,k$ の数とする.
今,長さ $N$ の文字列 $A,B$ が与えられる.
また,$Q$ 個のクエリが与えられるので,それに答える問題.
各クエリでは,$X,Y,L$ が与えられるので,文字列 $A[X,X+L-1], B[Y,Y+L-1]$ の類似度を求める.

解法

ダブリングを用いて,$f(x,y,k) = {}$ 文字列 $A[x,x+2^k-1], B[y,y+2^k-1]$ の類似度を計算する.
時間計算量は $O(N^2 \log N + Q \log N)$ 程度.

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

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


Current time: 2017年09月21日05時00分58秒
Last modified: 2015年06月19日19時09分04秒 (by laycrs)
Tags: Competitive_Programming Sphere_Online_Judge SPOJ_Classical
トップページに戻る

Logged in as: unknown user (not login)

ログイン: