結果

問題 No.515 典型LCP
コンテスト
ユーザー convexineq
提出日時 2021-02-11 01:38:33
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,317 bytes
コンパイル時間 150 ms
コンパイル使用メモリ 82,000 KB
実行使用メモリ 174,804 KB
最終ジャッジ日時 2024-07-08 13:21:40
合計ジャッジ時間 5,133 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD1 = 10**9+7
MOD2 = 10**9+9
b1 = 9997
b2 = 12345
class RollingHash:
    def __init__(self, s):
        self.n = len(s)
        if type(s) == str:
            self.S = [ord(i) for i in s]
        else:
            self.S = s[:]
        self.hs1 = [0]*(self.n+1)
        self.hs2 = [0]*(self.n+1)
        self.pw1 = [1]*(len(s)+1)
        self.pw2 = [1]*(len(s)+1)
        for i in range(self.n):
            self.hs1[i+1] = (self.hs1[i]*b1 + self.S[i])%MOD1
            self.hs2[i+1] = (self.hs2[i]*b2 + self.S[i])%MOD2
            self.pw1[i+1] = self.pw1[i]*b1%MOD1
            self.pw2[i+1] = self.pw2[i]*b2%MOD2

    #部分文字列 [l,r)のハッシュをとる
    def get_hash1(self,l,r):        
        return (self.hs1[r]-self.hs1[l]*self.pw1[r-l])%MOD1
    def get_hash2(self,l,r):        
        return (self.hs2[r]-self.hs2[l]*self.pw2[r-l])%MOD2

    def issame(self,l1,r1,l2,r2):
        return self.get_hash1(l1,r1) == self.get_hash1(l2,r2) and self.get_hash2(l1,r1) == self.get_hash2(l2,r2)
    
    # 先頭何文字が同じ？その数を返す
    def same_prefix(self,l1,r1,l2,r2):
        ok = 0
        ng = min(r1-l1,r2-l2) + 1
        while ng-ok > 1:
            mid = (ok+ng)//2
            if self.issame(l1,l1+mid,l2,l2+mid):
                ok = mid
            else:
                ng = mid
        return ok        

    # 末尾何文字が同じ？その数を返す
    def same_suffix(self,l1,r1,l2,r2):
        ok = 0
        ng = min(r1-l1,r2-l2) + 1
        while ng-ok > 1:
            mid = (ok+ng)//2
            if self.issame(r1-mid,r1,r2-mid,r2):
                ok = mid
            else:
                ng = mid
        return ok        



n,*s,m,x,d = open(0).read().split()
n,x,d = int(n),int(x),int(d)
R = [RollingHash(si) for si in s]

def issame(i,j,mid):
    return R[i].get_hash1(0,mid) == R[j].get_hash1(0,mid) and R[i].get_hash2(0,mid) == R[j].get_hash2(0,mid)

def same_prefix(i,j):
    ok = 0
    ng = min(len(s[i]),len(s[j]))+1
    while ng-ok > 1:
        mid = (ok+ng)//2
        if issame(i,j,mid):
            ok = mid
        else:
            ng = mid
    return ok        

ans = 0
for _ in range(1,int(m)+1):
    i = x//(n-1)
    j = x%(n-1)
    if i>j: i,j = j,i
    else: j += 1
    x = (x+d)%(n*(n-1))
    ans += same_prefix(i,j)
print(ans)
0