题目链接: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 ;
}

最新文章

  1. codeblocks个性化配置
  2. java导入excel时遇到的版本问题
  3. Rac grid用户启停监听报错无权限
  4. android第三方框架 xlistview 的使用
  5. cer pfx格式数字证书区别
  6. MongoDB.WebIDE:升级版的Mongodb管理工具
  7. 算法第四版 在Eclipse中调用Algs4库
  8. 转:SqlServer2008误操作数据(delete或者update)后恢复数据
  9. Android5.0之CardView的使用
  10. git stash的使用
  11. hibernate中有时候复杂删除有时候可以拆分为两个语句
  12. python之3内置容器
  13. wordpress 首页模板变量对应表
  14. HTML5 Introduction
  15. Unity 3D Framework Designing(4)——设计可复用的SubView和SubViewModel(Part 2)
  16. Could note find result map com.xxxx.entity.UserAccountDO
  17. Vue的使用
  18. JDBC连接MariaDB:数据传输加密
  19. pycharm 序列号/行号 的宽度太宽了如何调整
  20. 「SHOI2014」三叉神经树 解题报告

热门文章

  1. 为什么一定要学习linux系统?
  2. EJB3.0之事务
  3. vue 图片切换动态绑定
  4. C# 设置最顶层窗口。TopMostWindow
  5. 【强化学习】用pandas 与 numpy 分别实现 q-learning, saras, saras(lambda)算法
  6. Java性能优化之编程技巧总结
  7. Java的并发及锁
  8. JMX,Jstatd做好JVM应用上线的最后一层保障
  9. 使用go mod结合docker分层缓存进行自动CI/CD
  10. Leetcode 143. Reorder List(Medium)