博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
KMP笔记
阅读量:5017 次
发布时间:2019-06-12

本文共 472 字,大约阅读时间需要 1 分钟。

 

自匹配理解:正常操作(不用kmp)O(len^2),kmp有点像dp,在匹配第n位时用前n-1位匹配好的表,

      最后半写next半自匹配,完成了一个完整的自身与自身的kmp(它在匹配时只用到了已经算出来的部分next)

为什么只用了已经算出来的(解释):     

      代码pre_kmp中每次写next都是写在next[++i]里的,因为next的含义是在当前位置匹配失败时到转到的位置,

      假设失败的位置是p,转到的位置是x,要满足的条件是1~x-1和(p-x+1)~(p-1)一样的,所以反过来,字符串一样了,

      它是给后一维用的;

char a[maxn];int next[maxn];char b[maxn];//b自身的匹配表 void pre_kmp(char *a,int len,int *next) {    int i=0,j;    next[0]=j=-1;    while(i

 

转载于:https://www.cnblogs.com/Gsimt/p/8029400.html

你可能感兴趣的文章
如何创建表格,创建行和列
查看>>
数据结构之二叉树与树、森林转换
查看>>
angularjs+requirejs整合
查看>>
edit界面初始化加默认值
查看>>
Firefox 设置技巧
查看>>
UNIX环境编程学习——反思认识
查看>>
Esper epl语句实验
查看>>
怎样自学编程——“三遍读书法”
查看>>
Python模拟登录wap版百度贴吧+自己主动回贴
查看>>
常用DOS命令
查看>>
DHCP 服务配置
查看>>
关于ubuntu16.04系统无法系统更新的解决
查看>>
Windows7 64bit+python3.6环境下安装OpenCV3.3
查看>>
android TextView异常换行层次不齐的问题
查看>>
大话设计模式之模板方法模式
查看>>
The Final
查看>>
c# sealed修饰符
查看>>
Ajax模式2
查看>>
Spring演示及总结
查看>>
Android用Intent和Bundle传list
查看>>