CodeForces 113B Petr#
2024-08-26 10:06:30
题目链接:http://codeforces.com/problemset/problem/113/B
题目大意:
多组数据
每组给定3个字符串T,Sbeg,Sed,求字符串T中有多少子串是以Sbeg开头,Sed结尾的
分析:
难点在哈希函数的编写,如果直接存string会爆内存,不能用STL自带哈希函数,用了会Wa。
代码如下:
#include <bits/stdc++.h>
using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define rFor(i,t,s) for (int i = (t); i >= (s); --i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
#define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i) #define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl #define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin()) #define ms0(a) memset(a,0,sizeof(a))
#define msI(a) memset(a,inf,sizeof(a)) #define pii pair<int,int>
#define piii pair<pair<int,int>,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second inline int gc(){
static const int BUF = 1e7;
static char buf[BUF], *bg = buf + BUF, *ed = bg; if(bg == ed) fread(bg = buf, , BUF, stdin);
return *bg++;
} inline int ri(){
int x = , f = , c = gc();
for(; c<||c>; f = c=='-'?-:f, c=gc());
for(; c>&&c<; x = x* + c - , c=gc());
return x*f;
} typedef long long LL;
typedef unsigned long long uLL;
const LL mod = 1e9 + ;
const int maxN = + ; string T, Sbeg, Sed;
unordered_set< LL > sll;
int beg[maxN], begLen; // 记录 Sbeg出现的位置
int ed[maxN], edLen; // 记录 Sed出现的位置 // h为T的后缀哈希数组
// h[i]表示T从i位置开始的后缀的哈希值
// h[i] = T[i] + T[i+1]*key + T[i+2]*key^2 + ……+ T[i+len-1-i]*key^len-1-i
// xp为基数数组
// xp[i] = key^i
LL xp[maxN], h[maxN];
const LL key = 1e9 + ; // 求起点为s,长为len的子串的哈希值
// Hash(i, len) = T[i] + T[i+1]*key + T[i+2]*key^2 + ……+ T[i+len-1]*key^len-1
LL Hash(int s, int len) {
return h[s] - h[s + len] * xp[len];
} void HashInit(const char* s, LL* h, int len) {
xp[] = ;
For(i, , maxN - ) xp[i] = xp[i - ] * key; h[len] = ;
rFor(i, len - , ) h[i] = h[i + ] * key + s[i];
} int main(){
while(cin >> T >> Sbeg >> Sed) {
HashInit(T.c_str(), h, (int)T.size()); int ans = ;
sll.clear();
begLen = edLen = ; int p = ;
while(p < T.size()) {
int t = T.find(Sbeg.c_str(), p);
if(t == string::npos) break;
beg[begLen++] = t;
p = t + ;
} p = ;
while(p < T.size()) {
int t = T.find(Sed.c_str(), p);
if(t == string::npos) break;
ed[edLen++] = t;
p = t + ;
} int i = , j = ;
while(i < begLen && j < edLen) {
if(beg[i] <= ed[j]) {
For(k, j, edLen - ) {
if(beg[i] + Sbeg.size() > ed[k] + Sed.size()) continue;
sll.insert(Hash(beg[i], ed[k] + Sed.size() - beg[i]));
}
++i;
}
else ++j;
} cout << sll.size() << endl;
}
return ;
}
最新文章
- codeblocks个性化配置
- java导入excel时遇到的版本问题
- Rac grid用户启停监听报错无权限
- android第三方框架 xlistview 的使用
- cer pfx格式数字证书区别
- MongoDB.WebIDE:升级版的Mongodb管理工具
- 算法第四版 在Eclipse中调用Algs4库
- 转:SqlServer2008误操作数据(delete或者update)后恢复数据
- Android5.0之CardView的使用
- git stash的使用
- hibernate中有时候复杂删除有时候可以拆分为两个语句
- python之3内置容器
- wordpress 首页模板变量对应表
- HTML5 Introduction
- Unity 3D Framework Designing(4)——设计可复用的SubView和SubViewModel(Part 2)
- Could note find result map com.xxxx.entity.UserAccountDO
- Vue的使用
- JDBC连接MariaDB:数据传输加密
- pycharm 序列号/行号 的宽度太宽了如何调整
- 「SHOI2014」三叉神经树 解题报告