e270: PA. Aho-Corasick Automaton (AC ⾃動機)
Tags :
Accepted rate : 3人/5人 ( 60% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-07-07 13:03

Content

⾃動機是有限狀態機(FSM)的數學模型。FSM 是給定符號輸⼊,依據(可表達為⼀個表格的)轉移函式「跳轉」過⼀系列狀態的⼀種機器。逐個讀取輸⼊中的符號,直到被完全耗盡(把它當作有⼀個字寫在其上的磁帶,通過⾃動機的讀磁頭來讀取它;磁頭在磁帶上前⾏移動,⼀次讀⼀個符號)。⼀旦輸⼊被耗盡,⾃動機被稱為「停⽌」了。

依賴⾃動機停⽌時的狀態,稱呼這個⾃動機要麼是「接受」要麼「拒絕」這個輸⼊。如果停⽌於「接受狀態」,則⾃動機「接受」了這個字。在另⼀⽅⾯,如果它停⽌於「拒絕狀態」,則這個字被「拒絕」。⾃動機接受的所有字的集合被稱為「這個⾃動機接受的語⾔」。

⽽Aho-Corasick ⾃動機是⼀種⽤於處理多重匹配的資料結構,⽤以尋找多個⼩字串在⼀個⼤字串中出現各幾次,原本使⽤KMP演算法時,可能需要⼩字串數量乘上⼤字串⻑度的時間,但運⽤Aho-Corasick ⾃動機則會減少到與輸⼊⻑度相當,Aho-Corasick ⾃動機算⼀個KMP演算法的⼀個擴展,具體做法是將所有⼩字串做成⼀個字典樹(trie),⽽KMP的fail function,在這裡則變為失敗指針,會指向後綴匹配最⻑的⼀個節點。

漢克的教授指派給漢克很多個程式的原始碼去做⼀些處理,漢克發現如果我們能統計出這些程式碼的保留字元,之後再做⼀些簡單的處理就可以交差這些事情了,漢克建好⼀個保留字的Aho_Corasick ⾃動機,經過他的測試以後,他發現⼀個⻑度為$S$的字串會需要$S$單位的時間,之後教授指派給他很數組程式,第$i$組程式會有$x_i$個⻑度為$y_i$的程式且這組程式最晚交差時間是在$d_i$,漢克發現時間已經不夠了,他只能處理盡量多“個” 程式,且每個程式需要在所屬的那組的交差時間內完成,請你寫個程式幫助漢克計算他最多可以處理幾”個”程式。

Input

輸⼊第⼀⾏為⼀整數$T$代表接下來有幾組測試資料,接下來每⼀組測試資料第⼀⾏為⼀正整數$n$,代表有幾組程式需要處理,接下來有$n$⾏,每⾏有三個整數$x_i$, $y_i$, $d_i$,代表這組程式有$x_i$個⻑度為$y_i$的程式,且這組程式最晚交差時間為$d_i$。

$T \leq 20$

$n \leq 10^5$

$x_i, y_i \leq 10^9$

$d_i \leq 10^{18}$

Output

每⼀筆測試資料輸出⼀⾏代表最多可以處理多少“個”程式。

Sample Input
1
5
2 1 3
5 10 50
7 1 90
10 2 20
12 1 100
Sample Output
33
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <50M
Hint :

我們可以照順序處理第⼀組全部,第四組9 個,第⼆組3 個,第五組全部,第三組全部,總共33 個。

Tags:
出處:
2019 NCTU PCCA Winter [管理者:
qqrainbow (愛蜜莉雅 準•學測戰士)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」