結果
問題 | No.430 文字列検索 |
ユーザー | むらため |
提出日時 | 2019-01-30 22:10:18 |
言語 | Nim (2.0.2) |
結果 |
AC
|
実行時間 | 163 ms / 2,000 ms |
コード長 | 1,868 bytes |
コンパイル時間 | 3,620 ms |
コンパイル使用メモリ | 64,616 KB |
実行使用メモリ | 19,584 KB |
最終ジャッジ日時 | 2024-11-10 00:21:58 |
合計ジャッジ時間 | 5,450 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 163 ms
19,456 KB |
testcase_02 | AC | 42 ms
19,456 KB |
testcase_03 | AC | 105 ms
19,456 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 1 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 155 ms
19,584 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 14 ms
5,248 KB |
testcase_11 | AC | 150 ms
19,584 KB |
testcase_12 | AC | 148 ms
19,456 KB |
testcase_13 | AC | 151 ms
19,456 KB |
testcase_14 | AC | 143 ms
19,456 KB |
testcase_15 | AC | 138 ms
19,456 KB |
testcase_16 | AC | 91 ms
19,456 KB |
testcase_17 | AC | 70 ms
19,456 KB |
ソースコード
import sequtils,algorithm template times*(n:int,body) = (for _ in 0..<n: body) proc getchar_unlocked():char {. importc:"getchar_unlocked",header: "<stdio.h>" .} proc scan(): int = while true: let k = getchar_unlocked() if k < '0': break result = 10 * result + k.ord - '0'.ord template useRollingHash() = type RollingHash = object A,B: seq[int] AP,BP: seq[int] modA,modB : int baseA,baseB : int proc initRollingHash( S:string, baseA:int=17, baseB:int=19, modA:int=1_0000_0000_7.int, modB:int=1_0000_0000_9.int) : RollingHash = result.baseA = baseA result.baseB = baseB result.modA = modA result.modB = modB result.A = newSeq[int](S.len + 1) # baseA 進数表示した時の値 result.B = newSeq[int](S.len + 1) result.AP = newSeq[int](S.len + 1) # base^n result.BP = newSeq[int](S.len + 1) result.AP[0] = 1 result.BP[0] = 1 for i in 0..<S.len: result.A[i+1] = (result.A[i] * baseA + S[i].ord) mod modA for i in 0..<S.len: result.B[i+1] = (result.B[i] * baseB + S[i].ord) mod modB for i in 0..<S.len: result.AP[i+1] = (result.AP[i] * baseA) mod modA for i in 0..<S.len: result.BP[i+1] = (result.BP[i] * baseB) mod modB proc hash(self:RollingHash,l,r:int):(int,int) = # [l,r) ((self.AP[r-l] * self.A[l] - self.A[r] + self.modA) mod self.modA, (self.BP[r-l] * self.B[l] - self.B[r] + self.modB) mod self.modB) # 67800 と 678 は 67800 == 678 * 100 で得られる useRollingHash() let S = stdin.readLine() let m = scan() let RH = S.initRollingHash() var H = newSeqWith(11,newSeq[(int,int)]()) for i in 1..10: for j in 0..S.len-i: H[i] &= RH.hash(j,j+i) for i in 1..10: H[i].sort(cmp) var ans = 0 m.times: let S2 = stdin.readLine() let h = S2.initRollingHash().hash(0,S2.len) ans += H[S2.len].upperBound(h) - H[S2.len].lowerBound(h) echo ans