結果
問題 |
No.2361 Many String Compare Queries
|
ユーザー |
![]() |
提出日時 | 2025-06-12 21:44:27 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,381 bytes |
コンパイル時間 | 536 ms |
コンパイル使用メモリ | 81,960 KB |
実行使用メモリ | 74,624 KB |
最終ジャッジ日時 | 2025-06-12 21:48:55 |
合計ジャッジ時間 | 5,853 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 2 RE * 4 TLE * 1 -- * 7 |
ソースコード
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()