数据结构———KMP

时间:2022-09-24 07:38:17

今天照着课本敲了一下KMP..

以OJ上的一个题为例敲了一下。。

题目:http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2125

 #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; int nextv[],len_s,len_t;
char s[],t[];
void get_nextv()
{
int i=,j=-;
nextv[]=-;
while(i<len_t)
{
if(j==-||t[i]==t[j])
{
++i; ++j;
if(t[i]!=t[j]) nextv[i]=j;
else nextv[i]=nextv[j];
}
else
j=nextv[j];
}
} int kmp()
{
int i=,j=;
while(i<len_s&&j<len_t)
{
if(j==-||s[i]==t[j])
{
++i; ++j;
}
else j=nextv[j];
}
if(j>=len_t) return ;
else return -;
}
int main()
{
while(scanf("%s%s",s,t)!=EOF)
{
len_s=strlen(s); len_t=strlen(t);
get_nextv();
if(kmp()!=-)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return ;
}

数据结构———KMP的更多相关文章

  1. 数据结构--KMP算法总结

    数据结构—KMP KMP算法用于解决两个字符串匹配的问题,但更多的时候用到的是next数组的含义,用到next数组的时候,大多是题目跟前后缀有关的 . 首先介绍KMP算法:(假定next数组已经学会, ...

  2. &lbrack;数据结构&rsqb;KMP小结

    KMP小结   By Wine93 2013.9 1.学习链接: http://www.matrix67.com/blog/archives/115 2.个人小结 1.KMP在字符串中匹配中起着巨大作 ...

  3. 【暑假】&lbrack;实用数据结构&rsqb;KMP

    KMP算法 KMP算法是字符串匹配算法,可以在O(n)的时间完成,算法包含两部分,分别是:构造适配函数与两串匹配. 失配边的使用大大提高了算法效率,可以理解为已经成功匹配的字符不在重新匹配,因为我们已 ...

  4. 实验数据结构——KMP算法Test&period;ming

    翻译计划     小明初学者C++,它确定了四个算术.关系运算符.逻辑运算.颂值操作.输入输出.使用简单的选择和循环结构.但他的英语不是很好,记住太多的保留字,他利用汉语拼音的保留字,小屋C++,发明 ...

  5. 大话数据结构——KMP算法(还存在问题)

    http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html /*#include& ...

  6. 数据结构——KMP算法

    算法介绍 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法).KMP算法的核心是利用 ...

  7. 数据结构KMP算法中手算next数组

    总结一下今天的收获(以王道数据结构书上的为例子,虽然我没看它上面的...):其中竖着的一列值是模式串前缀和后缀最长公共前缀. 最后求得的结果符合书上的结果,如果是以-1开头的话就不需要再加1,如果是以 ...

  8. 数据结构——KMP(串)

    KMP一个非常经典的字符串模式匹配算法,虽然网上有很多kmp算法的博客,但是为了更好的理解kmp我还是自己写了一遍(这个kmp的字符串存储是基于堆的(heap),和老师说的定长存储略有不同,字符串索引 ...

  9. 数据结构-kmp算法

    定义 改进字符串的匹配算法 关键:通过实现一个包含了模式串的局部匹配信息的next()函数,利用匹配失败的信息,减少匹配次数. 1.BF算法 暴力匹配 给定 文本串S "BBC ABCDAB ...

随机推荐

  1. iOS 多快好省的宏定义

    http://my.oschina.net/yongbin45/blog/150149 // 字符串:#ifndef nilToEmpty#define nilToEmpty(object) (obj ...

  2. win 8 安装 NET framework3&period;5 方法

    win 8 预装的 NET framework 是 4.5 的,实际上很多程序要求的是 3.5,一般要另从网上下载的才能安装. 这里提供不需要从网上安装 .Net 3.5 的方法: 1.将 win 8 ...

  3. CF&num; Educational Codeforces Round 3 D&period; Gadgets for dollars and pounds

    D. Gadgets for dollars and pounds time limit per test 2 seconds memory limit per test 256 megabytes ...

  4. C&num;中如何按字节数截取字符串?

    http://www.cnblogs.com/xuejie/archive/2012/12/14/2818452.html

  5. Mysql 卡死的处理办理

    使用用show processlist 命令进去数据库查 或者用phpMyAdmin查也可以 .

  6. Qt ------ linux&lpar;ubuntu&rpar; 下用 linuxdeployqt 打包发布程序

    https://github.com/probonopd/linuxdeployqt/releases 1.下载linuxdeployqt 2.把下载的文件放入 /usr/local/bin 内,并执 ...

  7. groovy Date 格式化

    刚开始使用Java,瞬间爱上:换了个厂接触到了groovy,开始有点嫌弃Java了... 看看时间的格式化 java玩法: new SimpleDateFormat("yyyy-MM-dd ...

  8. Git 使用规范流程【转】

    转自:http://www.ruanyifeng.com/blog/2015/08/git-use-process.html 作者: 阮一峰 日期: 2015年8月 5日 团队开发中,遵循一个合理.清 ...

  9. JAVA高级之路----JAVA多线程

    介绍 这段时间一直在学习和整理一些通往java高级程序猿必备的知识点,有些是工作中必须要知道的,有些是面试必须要知道的, 但是不管怎么样,学习了就不会有坏处,不可能全部记得住,最起码得雁过留痕,知识不 ...

  10. 问题13:如何在for语句中迭代多个可迭代的对象

    from random import randint a1 = [randint(10, 50) for _ in range(5)] a2 = [randint(10, 50) for _ in r ...