文字列 $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)$ 程度．
この部分を表示するには表示権限を持つユーザーでログインする必要があります．
Current time: 2024年04月20日03時01分38秒
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)