CodeForces - 914F Substrings in a String
题意： 给定一个字符串s s s， q q q 次操作：①1 , i , c 1, i, c 1,i,c，将s i s_i si? 改为c c c；②2 , l , r , t 2, l, r, t 2,l,r,t，求串t t t 在s [ l ? r ] s[l\cdots r] s[l?r] 中出现的次数。 ( ∣ s ∣ ,q ,Σ ∣ t ∣ ≤ 1 0 5 ) (|s|,~q,~\Sigma |t| \leq 10^5) (∣s∣, q, Σ∣t∣≤105)
链接： https://codeforces.com/problemset/problem/914/F
解题思路： 可以根据串长分类，得到一个带根号的做法，即分块建立S A M SAM SAM，串长大于n \sqrt{n} n ? 时k m p kmp kmp 匹配，这一部分复杂度O ( n n ) O(n\sqrt{n}) O(nn ?)；否则整块跑S A M SAM SAM，横跨整块的匹配依然用k m p kmp kmp 来解决，散块部分也使用k m p kmp kmp，串长∣ t ∣ |t| ∣t∣，处理整块O ( ∣ t ∣ n ) O(|t| \sqrt{n}) O(∣t∣n ?)，处理横跨整块的匹配，只需讨论横跨处2 ∣ t ∣ 2|t| 2∣t∣ 长的主串O ( ∣ t ∣ n ) O(|t|\sqrt{n}) O(∣t∣n ?)，散块O ( ∣ t ∣ ) O(|t|) O(∣t∣)。修改操作则暴力重建S A M SAM SAM。那么总复杂度O ( n n ) O(n\sqrt{n}) O(nn ?)。
【CodeForces - 914F Substrings in a String】然而，牛客上做过这种题，我们可以有O ( n 2 32 ) O(\frac{n^2}{32}) O(32n2?) 的做法，用b i t s e t bitset bitset 暴力匹配，即预处理串s s s 每种字符出现的下标集合，当有匹配时， t i t_i ti? 在s s s 中出现的下标必然是t i ? 1 t_{i - 1} ti?1? 在s s s 中出现下标+ 1 +1 +1，那么令匹配下标初始化为t 1 t_1 t1? 在s s s 中出现的下标集合，每次& \& & 上对应的需要满足的下标集合即可。
参考代码：
#include
using namespace std;
typedef long long ll;
typedef pair pii;
#define sz(a) ((int)a.size())
#define pb push_back
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define gmid (l + r >> 1)
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
char s[maxn], t[maxn];
bitset bs[26], msk, ret;
int n, q;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
msk.set();
cin >> s;
n = strlen(s);
for(int i = 0;
i < n;
++i){
bs[s[i] - 'a'].set(i);
}
cin >> q;
while(q--){int opt, x, y;
cin >> opt >> x;
if(opt == 1){
cin >> t;
--x;
bs[s[x] - 'a'].reset(x);
s[x] = t[0];
bs[s[x] - 'a'].set(x);
}
else{
cin >> y >> t;
--x, --y;
int m = strlen(t);
int l = x, r = y - m + 1;
if(l > r){
cout << "0\n";
continue;
}
ret = bs[t[0] - 'a'] & (msk << l) & (msk >> (maxn - r - 1));
for(int i = 1;
i < m;
++i){
ret <<= 1;
ret &= bs[t[i] - 'a'];
}
cout << ret.count() << "\n";
}
}
return 0;
}
推荐阅读
- codeforces B. Young Explorers
- codeforces C. Mere Array
- codeforces D. Omkar and Bed Wars
- codeforces C. Omkar and Waterslide
- codeforces B. Omkar and Infinity Clock
- codeforces B. Ternary Sequence
- Codeforces580|Codeforces580 D. Kefa and Dishes（状压dp）
- Codeforces22|Codeforces22 D. Segments（贪心）
- codeforces|codeforces 667C C. Reberland Linguistics(dp)
- Codeforces|Codeforces Round #263 Div.1 B Appleman and Tree --树形DP【转】