- 浏览: 118625 次
- 性别:
- 来自: 北京
最新评论
// bjtu1394.cpp #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <iostream> #include <algorithm> #include <vector> #include <map> #include <set> #define out(v) cout << #v << ": " << (v) << endl #define SZ(v) ((int)(v).size()) using namespace std; typedef long long LL; int CS; char W[10000 + 5]; char T[1000000 + 5]; int LW, LT; int next[10000 + 5]; void getnext() { next[0] = -1; // 算到LW是有必要的,多次匹配时会用到 for (int i = 1, j = -1; i <= LW; ++i) { while (j != -1 && W[j] != W[i - 1]) j = next[j]; next[i] = ++j; } } int main() { scanf("%d", &CS); getchar(); while (CS--) { gets(W); LW = strlen(W); gets(T); LT = strlen(T); getnext(); int i = 0, j = 0, cnt = 0; while (i < LT) { while (j != -1 && T[i] != W[j]) j = next[j]; ++i, ++j; if (j == LW) { ++cnt; j = next[j]; } } printf("%d\n", cnt); } return 0; }
发表评论
-
lower_bound and upper_bound
2012-02-09 00:36 1158/** * @brief Finds the ... -
HDU 3954
2012-02-05 10:43 844线段树变种,也是在2logn段上面做文章 /* * ... -
HDU 4027
2012-02-04 22:09 857线段树变种 在2logn段上面做文章,swap(x, y)太阴 ... -
ICPC编码建议
2011-10-28 09:52 892写代码最重要的是清晰,包括思路的清晰和代码结构的清晰。我们无法 ... -
[转载]TopCoder插件
2011-09-08 22:13 978转载自:http://acm.cugb.edu.cn/blog ... -
UVALive 5112 - Sales Prediction
2011-01-06 10:19 1191封装了矩阵类 比赛做得很郁闷,为什么别人写得很长、很罗嗦的代码 ... -
hdu 3236
2010-12-12 14:10 800终于能过这道题了,算是背包必做题之一吧 /* * Au ... -
pku 1018
2010-12-11 15:18 604写了两三个版本,最后这个效率最高 #include < ... -
布斯(Booth)乘法
2010-10-07 19:59 1142源自http://watashi.ws/blog/1515/z ... -
高斯消元
2010-10-07 14:18 805import java.util.*; import j ... -
整数划分
2010-10-07 10:38 842#include <cstdio> #inc ... -
Treap
2010-09-18 22:19 982// Treap // Tested: bjtu1057 ... -
矩阵快速幂
2010-09-18 14:24 1053typedef LL matrix[55][55]; ... -
maximum clique 最大团
2010-09-02 18:12 1136最大团模板 #include <cstdio> ... -
计算Jacobi符号
2010-08-31 13:15 1298Quadratic reciprocity The Jacob ... -
Java 高效I/O
2010-08-19 16:54 780static BufferedReader cin = ... -
DLX pku 3076
2010-08-11 23:45 881标准数独,精确覆盖 // pku3076.cpp #in ... -
DLX hust 1017
2010-08-11 16:50 850“精确覆盖”问题 #include <cstdio& ... -
DLX hdu 3498
2010-08-11 16:48 1043“多重覆盖”或“重复覆盖”问题 #include < ... -
hdu 3509
2010-08-09 11:22 1007推导公式的题目,矩阵幂关键就在于构造系数矩阵 备忘: S(n, ...
相关推荐
KMP算法的板子
kmp算法模板与应用.txt
acm算法模板之kmp模板,对关键代码做了注释,帮助小白理解
用C++语言实现的KMP算法。经过调试。供广大算法学习者参考。
kmp 算法
C++编程语言虽然功能强大,应用方式灵活,但是在实际编程中同样会出现各种各样的错误。在这里我们将会为大家详细介绍一下有关C++指针漂移的解决方法,希望本文介绍的内容可以帮助大家解决问题。
kmp 算法 模版 kmp 算法 模版
开源学习吧,大家觉得有什么可以改的可以私信或者私聊我喔,我里面也有一点小bug,目前不知道怎么解决,有大佬可以解释的话,万分感谢捏。终于搞懂KMP了,不容易呀,哈哈哈哈!
本人写的kmp算法模板,能够给新手直接套模板减少写代码的时间,希望对大家有帮助
本文介绍了KMP算法的原理和基本实现方法,附带算法模板的代码和详解。如想了解更多内容,欢迎关注微信公众号:信息学竞赛从入门到巅峰。
KMP算法主要用于计算字符串间的匹配,可以说是ACM竞赛中经常出现的问题,掌握了模板,遇到问题迎刃而解
常用算法模板_C++.zip AC自动机,Dijkstra,Floyd,GCD,KMP,KMP扩展,Kruskal,LCM,LCS,LIS,Prim,SPFA,埃氏筛,背包,并查集,多边形面积,二分搜索,高精度加法,高精度阶乘,级角排序,进制转换,快速幂,...
ACM 算法模板集 Contents 一. 常用函数与STL 二. 重要公式与定理 1. Fibonacci Number 2. Lucas Number 3. Catalan Number 4. Stirling Number(Second Kind) 5. Bell Number 6. Stirling's Approximation 7. Sum of ...
KMP算法,是由Knuth,Morris,Pratt共同提出的模式匹配算法,其对于任何模式和目标序列,都可以在线性时间内完成匹配查找,而不会发生退化,是一个非常优秀的模式匹配算法。 分析:KMP模板题、KMP的关键是求出next的...
算法,字符串进阶,KMP算法题以及模板,ACM题,KMP模板
用于打比赛的ACM算法模板 常用函数与STL 重要公式与定理 1. Fibonacci Number 2. Lucas Number 3. Catalan Number 4. Stirling Number(Second Kind) 5. Bell Number 6. Stirling's Approximation 7. Sum of ...
树状数组 经典算法题每日演练——第九题 优先队列 经典算法题每日演练——第八题 AC自动机 经典算法题每日演练——第七题 KMP算法 经典算法题每日演练——第六题 协同推荐SlopeOne 算法 经典算法题每日演练——第五...
北航17级算法上机自己整理的模板,发给大家参考(动态规划、贪心、计算几何、最大流、二分图最大匹配、归并排序、FFT、KMP)
本科参加ACM竞赛的过程中积累下来的一部分算法模板,和自己在PKU上面做的一部分题目。 模板目录结构: 目录: 动态规划 O(n^2)的最长上升子序列 nlogn最长上升子序列 高精度 计算几何 Graham扫描法 两线段交点 凸...