結果

問題 No.263 Common Palindromes Extra
ユーザー gew1fw
提出日時 2025-06-12 20:43:22
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,369 bytes
コンパイル時間 178 ms
コンパイル使用メモリ 82,080 KB
実行使用メモリ 656,656 KB
最終ジャッジ日時 2025-06-12 20:43:37
合計ジャッジ時間 9,314 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 WA * 6 MLE * 3 -- * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    S = input[0]
    T = input[1]
    
    MOD1 = 10**18 + 3
    MOD2 = 10**18 + 7
    P = 911382629
    Q = 3571428571
    
    max_len = max(len(S), len(T)) + 2
    powP = [1] * (max_len + 1)
    powQ = [1] * (max_len + 1)
    for i in range(1, max_len + 1):
        powP[i] = (powP[i-1] * P) % MOD1
        powQ[i] = (powQ[i-1] * Q) % MOD2
    
    def build_eertree(s, powP, powQ, MOD1, MOD2):
        nodes = []
        nodes.append({'length': -1, 'suffix_link': 0, 'transitions': {}, 'hash1': 0, 'hash2': 0, 'cnt': 0})
        nodes.append({'length': 0, 'suffix_link': 0, 'transitions': {}, 'hash1': 0, 'hash2': 0, 'cnt': 0})
        size = 2
        last = 1
        
        for idx, c in enumerate(s):
            current = last
            while True:
                pos = current
                edge = idx - nodes[pos]['length'] - 1
                if edge >= 0 and s[edge] == c:
                    break
                current = nodes[current]['suffix_link']
            
            if c in nodes[pos]['transitions']:
                last = nodes[pos]['transitions'][c]
                continue
            
            new_node = {
                'length': nodes[pos]['length'] + 2,
                'suffix_link': 0,
                'transitions': {},
                'hash1': 0,
                'hash2': 0,
                'cnt': 1
            }
            nodes.append(new_node)
            size += 1
            nodes[pos]['transitions'][c] = size - 1
            
            if new_node['length'] == 1:
                new_node['suffix_link'] = 1
            else:
                current_suffix = nodes[pos]['suffix_link']
                while True:
                    edge = idx - nodes[current_suffix]['length'] - 1
                    if edge >= 0 and s[edge] == c:
                        break
                    current_suffix = nodes[current_suffix]['suffix_link']
                new_node['suffix_link'] = nodes[current_suffix]['transitions'].get(c, 1)
            
            if new_node['length'] > 0:
                parent = nodes[new_node['suffix_link']]
                new_node['hash1'] = (ord(c) * powP[new_node['length'] - 1] + parent['hash1'] * P % MOD1 + ord(c)) % MOD1
                new_node['hash2'] = (ord(c) * powQ[new_node['length'] - 1] + parent['hash2'] * Q % MOD2 + ord(c)) % MOD2
            else:
                new_node['hash1'] = 0
                new_node['hash2'] = 0
            
            last = size - 1
        
        order = list(range(size))
        order.sort(key=lambda x: -nodes[x]['length'])
        
        for node_idx in order:
            sl = nodes[node_idx]['suffix_link']
            nodes[sl]['cnt'] += nodes[node_idx]['cnt']
        
        freq = {}
        for node in nodes:
            if node['length'] >= 1:
                h = (node['hash1'], node['hash2'])
                if h in freq:
                    freq[h] += node['cnt']
                else:
                    freq[h] = node['cnt']
        
        return freq
    
    freq_S = build_eertree(S, powP, powQ, MOD1, MOD2)
    freq_T = build_eertree(T, powP, powQ, MOD1, MOD2)
    
    result = 0
    for h in freq_S:
        if h in freq_T:
            result += freq_S[h] * freq_T[h]
    
    print(result)

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