Codecraft-18 and Codeforces Round #458 (Div. 1 + Div. 2, combined) F. Substrings in a String
2024-08-29 09:51:23
http://codeforces.com/contest/914/problem/F
以前做过一个类似的,但是查询的子串长度最多是10,这个时候就是用bit + hash做了。这是因为改变一个字符,只需改变它后面10个的hash值就够了,多余的不影响,因为查询去不到那里。(只记得是今年的网络赛来的)
但是这题查询只给了一个长度总和,没上一题好做。
这题的思路应该是用bitset查询。
把各个字母拆成不同的bitset,比如abc,拆成
a: 001
b: 010
c: 100
然后,a & (b >> 1) & (c >> 2)即可。
最后统计bitset的L + lent - 1,R区间中有多少个1,这里需要用移位加速,不然TLE.
bitset的第0位,是最右边的。这也刚好, 相当于把整个串反转了 >> 后也可以把不需要的剔除
>> L位,是把左边的无关字符去掉
>> (R - L + 2 - lent)位是可以算出来的
具体就是,从L开始,假设有x位是合法的贡献,那么有L + x - 1 + lent - 1 = R
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
const int MAXN = 1e5 + ;
bitset<MAXN> f[];
char str[MAXN];
char t[MAXN];
bitset<MAXN> getAns;
void work() {
scanf("%s", str + );
int lenstr = strlen(str + );
for (int i = ; i <= lenstr; ++i) f[str[i] - 'a'][i] = ;
int q;
scanf("%d", &q);
while (q--) {
int op;
scanf("%d", &op);
if (op == ) {
int pos;
scanf("%d%s", &pos, t);
f[str[pos] - 'a'][pos] = ;
str[pos] = t[];
f[str[pos] - 'a'][pos] = ;
} else {
int L, R;
scanf("%d%d%s", &L, &R, t + );
int lent = strlen(t + );
if (lent > R - L + ) {
printf("0\n");
continue;
}
getAns.reset();
getAns = ~getAns;
for (int i = ; i <= lent; ++i) {
getAns &= (f[t[i] - 'a'] >> (i - ));
}
// cout << getAns << endl;
getAns >>= L;
// cout << getAns << endl;
int ans = getAns.count();
getAns >>= (R - L + - lent);
// cout << getAns << endl;
ans -= getAns.count();
printf("%d\n", ans);
}
}
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}
最新文章
- C# Stream
- oracle deterministic 关键字
- java 面试每日一题7
- c# 之五行地支
- css规范大全
- SpriteParticle II
- 判断sqlserver临时表等临时资源是否存在
- (转)Phonegap VS AppCan
- 自己做个 Tag标签
- MySQL show master / slave status 命令参数
- 这是您一直期待的所有iOS 11功能的屏幕截图
- cnblog 模板 SimpleMemory 个性化设置代码备份
- C# ListView应用
- 用idea部署maven-web项目
- EOS 权限
- Postfix 邮件服务 - 邮箱组件 cyrus-sasl
- PL/SQL学习笔记之基本块格式与语法
- windows环境下搭建Java开发环境(一):jdk安装和配置
- HTTP协议GET和POST的区别
- oracle数据据 Python+Pandas 获取Oracle数据库并加入DataFrame