- 浏览: 120733 次
- 性别:
- 来自: 北京
最新评论
// 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 1189/** * @brief Finds the ... -
HDU 3954
2012-02-05 10:43 867线段树变种,也是在2logn段上面做文章 /* * ... -
HDU 4027
2012-02-04 22:09 890线段树变种 在2logn段上面做文章,swap(x, y)太阴 ... -
ICPC编码建议
2011-10-28 09:52 944写代码最重要的是清晰,包括思路的清晰和代码结构的清晰。我们无法 ... -
[转载]TopCoder插件
2011-09-08 22:13 1012转载自:http://acm.cugb.edu.cn/blog ... -
UVALive 5112 - Sales Prediction
2011-01-06 10:19 1223封装了矩阵类 比赛做得很郁闷,为什么别人写得很长、很罗嗦的代码 ... -
hdu 3236
2010-12-12 14:10 829终于能过这道题了,算是背包必做题之一吧 /* * Au ... -
pku 1018
2010-12-11 15:18 651写了两三个版本,最后这个效率最高 #include < ... -
布斯(Booth)乘法
2010-10-07 19:59 1175源自http://watashi.ws/blog/1515/z ... -
高斯消元
2010-10-07 14:18 838import java.util.*; import j ... -
整数划分
2010-10-07 10:38 861#include <cstdio> #inc ... -
Treap
2010-09-18 22:19 1012// Treap // Tested: bjtu1057 ... -
矩阵快速幂
2010-09-18 14:24 1074typedef LL matrix[55][55]; ... -
maximum clique 最大团
2010-09-02 18:12 1170最大团模板 #include <cstdio> ... -
计算Jacobi符号
2010-08-31 13:15 1339Quadratic reciprocity The Jacob ... -
Java 高效I/O
2010-08-19 16:54 811static BufferedReader cin = ... -
DLX pku 3076
2010-08-11 23:45 922标准数独,精确覆盖 // pku3076.cpp #in ... -
DLX hust 1017
2010-08-11 16:50 881“精确覆盖”问题 #include <cstdio& ... -
DLX hdu 3498
2010-08-11 16:48 1079“多重覆盖”或“重复覆盖”问题 #include < ... -
hdu 3509
2010-08-09 11:22 1030推导公式的题目,矩阵幂关键就在于构造系数矩阵 备忘: S(n, ...
相关推荐
**KMP算法实现模板(C++版) ACM算法** KMP(Knuth-Morris-Pratt)算法是一种在文本字符串中查找子串匹配的有效方法,尤其适用于已经预处理了模式串(子串)的匹配信息。它是由D.E. Knuth、V. Morris和J.H. Pratt...
kmp算法模板与应用.txt
用C++语言实现的KMP算法。经过调试。供广大算法学习者参考。
### KMP算法详解 #### 一、引言 在计算机科学中,字符串匹配问题是非常常见的。其中,KMP(Knuth-Morris-Pratt)算法是一种高效的字符串匹配算法,能够解决给定主串和模式串时如何快速找到模式串在主串中的位置...
KMP算法的板子
C++编程语言虽然功能强大,应用方式灵活,但是在实际编程中同样会出现各种各样的错误。在这里我们将会为大家详细介绍一下有关C++指针漂移的解决方法,希望本文介绍的内容可以帮助大家解决问题。
在字符串匹配问题中,KMP算法具有O(n)的时间复杂度,其中n是文本串的长度。 KMP算法的核心思想是处理模式串(要查找的子串)中的重复字符。当模式串与文本串比较时,如果遇到不匹配的情况,传统的方法会将模式串...
kmp 算法 模版 kmp 算法 模版
本人写的kmp算法模板,能够给新手直接套模板减少写代码的时间,希望对大家有帮助
本文介绍了KMP算法的原理和基本实现方法,附带算法模板的代码和详解。如想了解更多内容,欢迎关注微信公众号:信息学竞赛从入门到巅峰。
### KMP算法详解 #### 一、引言 在计算机科学中,字符串匹配是一个非常重要的问题,尤其是在文本处理、搜索引擎等领域。KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,它避免了传统匹配算法中的...
**KMP算法简介** KMP(Knuth-Morris-Pratt)算法是一种高效的字符串匹配算法,由D.E. Knuth、V.R. Morris和J.H. Pratt共同提出。它的核心思想在于利用模式串(要查找的子串)中的重复信息,避免在文本串中进行不必...
标题“NOIP基本算法模板”指向了信息学奥林匹克竞赛(NOIP)中常见的算法模板。NOIP竞赛是面向中学生的信息学竞赛,旨在考查学生的算法设计与编程能力。这一部分知识广泛适用于信息学竞赛的普及组和提高组,特别是用...
**KMP算法详解** KMP(Knuth-Morris-Pratt)算法是一种高效的字符串匹配算法,由D.E. Knuth、V.R. Pratt和J.W. Morris三人于1970年代提出。它解决了在主串(即目标文本)中查找子串(即模式串)的问题,无需回溯,...
- **KMP算法**:模式匹配算法,用于在文本中快速查找子串出现的位置。 - **Z算法**:另一种字符串匹配算法,可以找出所有子串的起始位置。 6. **数据结构** - **栈和队列**:C++中可通过`std::stack`和`std::...
6. **字符串处理**:包括KMP算法、Boyer-Moore算法等字符串匹配方法,以及Z函数、Manacher's算法等字符串处理技巧。 7. **图论算法**:Dijkstra's单源最短路径算法、Floyd-Warshall所有对最短路径算法,以及Ford-...
包括KMP算法及其拓展、字典树(Trie)、AC自动机等。这些算法在处理字符串匹配问题上非常高效,是很多搜索引擎和文本处理软件的基础。 12. 树状数组(Binary Indexed Tree)与线段树: 这两种数据结构用于高效地...
《浙江大学ACM算法模板》是针对ACM(国际大学生程序设计竞赛)的参赛者们精心编纂的一套学习资源,涵盖了C和C++语言的算法实现。这份模板旨在帮助参赛者快速理解和应用基础及高级算法,提升编程能力,提高解决实际...
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 ...