結果

問題 No.263 Common Palindromes Extra
ユーザー amesyuamesyu
提出日時 2024-10-19 15:27:53
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,694 bytes
コンパイル時間 682 ms
コンパイル使用メモリ 82,468 KB
実行使用メモリ 407,416 KB
最終ジャッジ日時 2024-10-19 15:28:03
合計ジャッジ時間 8,627 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 WA -
testcase_02 WA -
testcase_03 MLE -
testcase_04 MLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict

MOD = (1<<61) - 1
BASE = 10007
MAXN = 10**6
POWER = [1]
for i in range(1, MAXN+1):
    POWER.append((POWER[-1] * BASE) % MOD)

class RollingHash:
    def __init__(self, string):
        self.string = string
        self.size = len(string)
        
        # construct
        self.hashed = [0]
        for i in range(self.size):
            self.hashed.append(self.hashed[-1] * BASE + ord(self.string[i]))
            self.hashed[-1] %= MOD

    def query(self, l, r):
        assert 0 <= l <= r <= self.size
        return (self.hashed[r] - self.hashed[l] * POWER[r-l]) % MOD

def composite_query(R1, R2, l1, r1, l2, r2):
    LEFT = R1.query(l1, r1)
    RIGHT = R2.query(l2, r2)
    return (RIGHT + LEFT * POWER[r2-l2]) % MOD

class eertree:
    def __init__(self, string):
        self.string = string
        self.size = len(string)
        self.r1 = RollingHash(self.string)
        self.r2 = RollingHash(''.join(reversed(self.string)))
    
    def __rev(self, l, r):
        return self.size - r, self.size - l

    def build(self):
        
        BEGIN = ord('A') # or ord('a')
        # Centroid of the palindrome A-Z and ''
        ptr = [defaultdict(lambda: -2) for _ in range(27)]
        lazy = [defaultdict(int) for _ in range(27)]
        tail = [(-1, -1) for _ in range(27)]
        tail[26] = (0, 0)
        ptr[26][0] = -1

        for i in range(self.size):
            
            # Centroid = self.string[i]
            ok, ng = -1, min(i, self.size-i-1)+1
            ID = ord(self.string[i]) - BEGIN

            while ng - ok > 1:
                x = (ng + ok) >> 1
                h = self.r1.query(i+1, i+1+x)
                if ptr[ID][h] >= -1: ok = x
                else: ng = x
            
            if ok == -1:
                ptr[ID][0] = -1
                ok = 0

            prh = self.r1.query(i+1, i+1+ok)
            longest = ok
            for j in range(ok+1, min(i, self.size-i-1)+1):
                l1, r1 = i+1, i+1+j
                l2, r2 = self.__rev(i-j, i)
                h1 = self.r1.query(l1, r1)
                h2 = self.r2.query(l2, r2)
                if h1 == h2:
                    longest = j
                    ptr[ID][h1] = prh
                    prh = h1
                else:
                    break
            lazy[ID][prh] += 1
            tail[ID] = max(tail[ID], (longest, prh))

            # Centroid = ''
            ok, ng = 0, min(i, self.size-i-1) + 1
            ID = 26

            while ng - ok > 1:
                x = (ng + ok) >> 1
                h = self.r1.query(i, i + x)
                if ptr[ID][h] >= -1: ok = x
                else: ng = x

            prh = self.r1.query(i, i+ok)
            longest = ok
            for j in range(ok+1, min(i, self.size-i)+1):
                l1, r1 = i, i + j
                l2, r2 = self.__rev(i - j, i)
                h1 = self.r1.query(l1, r1)
                h2 = self.r2.query(l2, r2)
                if h1 == h2:
                    longest = j
                    ptr[ID][h1] = prh
                    prh = h1
                else:
                    break
            lazy[ID][prh] += 1
            tail[ID] = max(tail[ID], (longest, prh))
        
        for ID in range(27):
            _, v = tail[ID] 
            while v > 0:
                par = ptr[ID][v]
                lazy[ID][par] += lazy[ID][v]
                v = par

        lazy[26][0] = 0 
        return lazy

s = input()
t = input()

palS = eertree(s)
palT = eertree(t)
ResultS = palS.build()
ResultT = palT.build()

ans = 0
for ID in range(27):
    for h in ResultS[ID]:
        ans += ResultS[ID][h] * ResultT[ID][h]

print(ans)
0