結果

問題 No.2361 Many String Compare Queries
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 17:02:30
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,381 bytes
コンパイル時間 215 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 75,136 KB
最終ジャッジ日時 2025-06-12 17:02:36
合計ジャッジ時間 5,516 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 RE * 4 TLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    N, Q = map(int, sys.stdin.readline().split())
    S = sys.stdin.readline().strip()
    queries = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]
    
    # Precompute all prefix hashes for S using a rolling hash function (e.g., base=26, mod=10^18+3)
    mod = 10**18 + 3
    base = 911382629
    prefix_hash = [0] * (N + 1)
    power = [1] * (N + 1)
    for i in range(N):
        prefix_hash[i+1] = (prefix_hash[i] * base + ord(S[i])) % mod
        power[i+1] = (power[i] * base) % mod

    def get_hash(l, r):
        # Returns hash of S[l..r] (1-based, inclusive)
        res = (prefix_hash[r] - prefix_hash[l-1] * power[r - l + 1]) % mod
        return res if res >= 0 else res + mod

    for L, R in queries:
        T = S[L-1:R]
        m = len(T)
        count = 0

        # Case 1: Substrings that are a proper prefix of T
        # For each l from 1 to m-1, count the number of occurrences of T[0..l-1] in S
        # This is done using binary search on the suffix array for each prefix
        # However, due to time constraints, we approximate this by checking for occurrence in S
        # Note: This is not efficient and is only for demonstration
        for l in range(1, m):
            substr = T[:l]
            # Using a simple approach (inefficient for large N)
            # In practice, use a more efficient method like a suffix automaton
            cnt = 0
            for i in range(N - l + 1):
                if S[i:i+l] == substr:
                    cnt += 1
            count += cnt

        # Case 2: Substrings that have a differing character at some position k < l
        # This part is not implemented optimally and is only for demonstration
        # In practice, a more efficient method is needed
        for i in range(N):
            j = 0
            while j < min(m, N - i):
                if S[i + j] < T[j]:
                    count += (N - (i + j))
                    break
                elif S[i + j] > T[j]:
                    break
                j += 1
            else:
                if j == m:
                    # Substring starts at i and is equal to T, but not a prefix
                    pass
                else:
                    if S[i + j] < T[j]:
                        count += (N - (i + j))
        
        print(count)

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