結果

問題 No.263 Common Palindromes Extra
ユーザー gew1fw
提出日時 2025-06-12 19:17:57
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,148 bytes
コンパイル時間 396 ms
コンパイル使用メモリ 82,288 KB
実行使用メモリ 169,780 KB
最終ジャッジ日時 2025-06-12 19:18:04
合計ジャッジ時間 6,475 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

MOD1 = 10**9 + 7
BASE1 = 911382629
MOD2 = 10**9 + 9
BASE2 = 3571428571

def compute_prefix_hash(s, base, mod):
    n = len(s)
    prefix = [0] * (n + 1)
    pow_base = [1] * (n + 1)
    for i in range(n):
        prefix[i+1] = (prefix[i] * base + ord(s[i])) % mod
        pow_base[i+1] = (pow_base[i] * base) % mod
    return prefix, pow_base

def manacher(s):
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    d = [0] * n
    l, r = 0, -1
    for i in range(n):
        k = 1 if i > r else min(d[l + r - i], r - i + 1)
        while 0 <= i - k and i + k < n and t[i - k] == t[i + k]:
            k += 1
        d[i] = k
        if i + k - 1 > r:
            l = i - k + 1
            r = i + k - 1
    return t, d

def process_string(s):
    prefix1, pow1 = compute_prefix_hash(s, BASE1, MOD1)
    prefix2, pow2 = compute_prefix_hash(s, BASE2, MOD2)
    t, d = manacher(s)
    m = len(t)
    hash_count = defaultdict(int)
    
    for i in range(m):
        if i % 2 == 1:
            max_r = d[i]
            if max_r % 2 == 0:
                max_r -= 1
            if max_r < 1:
                continue
            for r_val in range(1, max_r + 1, 2):
                start = i - r_val + 1
                end = i + r_val - 1
                l_orig = (start - 1) // 2
                r_orig = (end - 1) // 2
                if l_orig < 0 or r_orig >= len(s) or l_orig > r_orig:
                    continue
                hash1 = (prefix1[r_orig + 1] - prefix1[l_orig] * pow1[r_orig - l_orig + 1]) % MOD1
                hash1 = (hash1 + MOD1) % MOD1
                hash2 = (prefix2[r_orig + 1] - prefix2[l_orig] * pow2[r_orig - l_orig + 1]) % MOD2
                hash2 = (hash2 + MOD2) % MOD2
                substring = s[l_orig:r_orig + 1]
                if substring == substring[::-1]:
                    hash_count[(hash1, hash2)] += 1
        else:
            max_r = d[i]
            if max_r % 2 != 0:
                max_r -= 1
            if max_r < 2:
                continue
            for r_val in range(2, max_r + 1, 2):
                start = i - r_val + 1
                end = i + r_val - 1
                l_orig = (start - 1) // 2
                r_orig = (end - 1) // 2
                if l_orig < 0 or r_orig >= len(s) or l_orig > r_orig:
                    continue
                hash1 = (prefix1[r_orig + 1] - prefix1[l_orig] * pow1[r_orig - l_orig + 1]) % MOD1
                hash1 = (hash1 + MOD1) % MOD1
                hash2 = (prefix2[r_orig + 1] - prefix2[l_orig] * pow2[r_orig - l_orig + 1]) % MOD2
                hash2 = (hash2 + MOD2) % MOD2
                substring = s[l_orig:r_orig + 1]
                if substring == substring[::-1]:
                    hash_count[(hash1, hash2)] += 1
    return hash_count

def main():
    s = sys.stdin.readline().strip()
    t = sys.stdin.readline().strip()
    
    count_S = process_string(s)
    count_T = process_string(t)
    
    result = 0
    for key in count_S:
        if key in count_T:
            result += count_S[key] * count_T[key]
    print(result)

if __name__ == "__main__":
    main()
0