bitset優化

bitset復雜度可以達到 \(O(n/32)\) ，一定程度上可以 \(n^2\) 過 \(10^5\) 。

例題CodeForces - 914F

題目問題在于統計 \(10^5\) 個 \(10^5\) 數量級的字符串匹配，傳統字符串哈希或kmp只能做到 \(O(n^2)\) 。可以考慮引入bitset優化。理由如下

1. 字符集較小，只包含小寫字母
2. \(\sum \lvert S \rvert <10^5\),總查詢長度較小
3. 不存在區間修改操作

bitset實現

考慮枚舉每一個小寫字母的位置，做成26個bitset。匹配時，先建一個全為1的bitset \(Ans\) ，考慮首字母的bitset相取&，即確定了所有可能首字母的位置。在匹配第 \(i\) 個，將 \(b_{s_i}\) 向左移 \(i\) 位后再與 \(Ans\) 取與。

代碼：

Ans.set();
for(int i=0;i<s.size();i++){
	Ans=Ans&(b[s[i]-'a'+1]>>i);
}

具體代碼具體代碼

分塊優化

傳統的字符串哈希復雜度為 \(O(n)\) ，對于有修改操作的字符串匹配來說，將哈希分塊處理復雜度大大減小。

例題還是：CodeForces - 914F

記錄 \(Hash_{i,j}\) 為字符串 \(S[i,i+j-1]\) 的哈希值，對于查詢字符串 \(X\) 來說，只需要匹配 \(Hash_{i,|x|}\) ，但。

未完待續