记住这张图,getnext就是对一个已知的待匹配的串进行分析,nex【i】表示当a【i】匹配失败后我能跳到哪里,继续尝试匹配,而不是每一次失败都从头再来,先来看看代码

const int maxn = 1e5;
int net[maxn];
char a[maxn];
void get_next(int len)
{
int i = 0,j = -1;
nex[0] = -1;//别忘记初始化,和汽车的发动机一样重要
while(i < len)
{
if(j == -1 || a[i] == a[j])
{
net[++i] = ++j;
}
else
{
j = net[j];
}
}
}

j = -1是一个特殊判断代表到了头是在不能尝试匹配了得从头开始了
而a[i] = a[j]的时候,就可已更新i + 1位的net数组,他能跳的位置也就是j + 1
当a[i] != a[j]的时候,我们也是寻找的它能跳的最大(远)的点,所以先跳到net[j]去尝试匹配,……直到j=-1不能配为止,那么net[i+1]=0,也只能从头开始了

———————————————————————————————————————————————

看HDU3336

让你求每一个前缀的出现次数,是对next数组意义的考察

看那个图:是在j位置失配时能跳到的最远的位置,前提是p0 --pk-1和pj-k--pj-1相同(匹配)才能跳到k-1+1的位置再次进行匹配,也就是每一个>0的next【i】都代表0——i-1的字符串内有匹配项,我们要考虑的是断开的位置,是next数组断开的位置,如果next[i] + 1 == next[i+1]的化,代表匹配项还没结束,还在一直匹配着,我们得到结束点,然后计算前缀重复出现的次数

注意这个题是不允许交叉计算的例如ababa中aba止出现了一次,所以对我们找到的部分最长匹配串,我们是不用考虑其内部还有子匹配串的情况的 ,因为会交叉
例如a  b  a  b  a  b

  -1 0  0  1  2  3  4

面对一整个串我们只能找到的是abab这个部分最长匹配串对应的next值是4,最后结果加的4对应的分别是a,ab,(ab)a,(ab)ab,这是存在交叉

时候的运算

不存在交叉的时候最好考虑了……

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
const int maxn = 200005; int net[maxn];
char a[maxn]; void get_next(int len) //KMP原始next值
{
int i = 0, j = -1;
net[0] = -1;
while (i < len)
{
if (j == -1 || a[i] == a[j])
{
net[++i] = ++j;
}
else j = net[j];
}
}
int main()
{
int t, res,len;
scanf("%d", &t);
while(t--)
{
scanf("%d",&len); scanf("%s",&a);
get_next(len);
res = net[len] + len;
for (int i = 0; i < len ; i++)
if (net[i] > 0 && net[i] + 1 != net[i+1])
res += net[i];
printf ("%d\n", res%10007);
}
return 0;
}

这个题不大好~~就这样草草结束吧
——————————————————————————————————————————————————

再来看一道2087这是在kmp这个题比较入门,正常的匹配过程中改变一下条件就好了4

int kmp(int len1,int len2)
{
int i = 0,j = 0,cnt = 0;
while(i < len1)
{
if(j == -1 || a[i] == b[j])
{
i++;
j++;
}
else
{
j = net[j];
}
if(j == len2)
{
j = 0;
cnt++;
}
}
return cnt;
}

然后HDU1867

考的是字符串相加,一个串的前缀和另一个串的后缀可以结合,优先输出结合后长度最小的,如果长度都相等,救输出字典序最小的

一开始我做的相当的麻烦,没有一点模块化编程的想法

实现模块化就是用一个函数实现a + b 和b + a 的结果

在这里用到了指针!!
在kmp中我们求net(因为net不像是原来的题目一样求一次就过了,他需要求b再求a)

然后是改编版的kmp:因为我们寻求的是前缀和后缀相同,所以为了避免完全包含的情况入abcbc 和 bc的出现我们while的条件是i<l1:也就是母串必须遍历到头,且注意对j 重新更新为0的判断(当j == l2 && i != l1)的时候才进行

然后返回j的位置,就是,匹配后我该输出的另一个的骑士位置

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define INF 0x3f3f3f3f
#define maxn 100000+10
using namespace std; char str1[maxn], str2[maxn];
int net[maxn]; void getnet(char *x,int len)
{
int i = 0,j = -1;
net[0] = -1;
while(i < len)
{
if(j == -1 || x[i] == x[j])
{
net[++i] = ++j;
}
else j =net[j];
}
}
int kmp(char *s1,char *s2)
{
int i = 0,j = 0;
int l1 = strlen(s1),l2 = strlen(s2);
getnet(s2,l2);
while( i < l1)
{
if(j == -1 || s1[i] == s2[j])i++,j++;
else j =net[j];
if(j == l2 && i != l1)() j = 0;
}
return j;
}
int main()
{
while(~scanf("%s",str1))
{
scanf("%s",str2);
int tem1 = kmp(str1,str2);
int tem2 = kmp(str2,str1);
if(tem1 > tem2)
{
printf("%s",str1);
printf("%s\n",&str2[tem1]);
}
else if(tem1 < tem2)
{
printf("%s",str2);
printf("%s\n",&str1[tem2]);
}
else
{
if(strcmp(str1,str2) < 0)printf("%s%s\n",str1,&str2[tem1]);
else printf("%s%s\n",str2,&str1[tem2]);
}
}
return 0 ;
}

最新文章

  1. saltstack学习
  2. winform里dataGridView分页代码,access数据库
  3. 第一个APP 时钟
  4. wdcp日志
  5. oracle的购买价格研究
  6. Keepalived + HAProxy 搭建【第一篇】HAProxy 的安装和配置
  7. FreeSql.Repository 通用仓储层功能
  8. 创建自定义的 Angular Schematics
  9. 用户登录三次机会(PYTHON)
  10. Codeforces 806 D. Perishable Roads Dijkstra
  11. 没有 iOS 开发者账号的情况下部署到真机的方法
  12. 自定义session的存储机制
  13. BZOJ.3680.吊打XXX(模拟退火/爬山算法)
  14. Linux查看当前网卡流量
  15. Vue中计算属性与class,style绑定
  16. day23 python学习 类 人狗大战
  17. 5.log4j报错
  18. WEB入门.八 背景特效
  19. 【不知道是啥的NOIP模拟赛】网络入侵
  20. 数据库——mysql如何获取当前时间

热门文章

  1. lintcode bugfree and good codestyle note
  2. 【腾讯Bugly干货分享】从0到1打造直播 App
  3. Shell 读取文本内容
  4. xampp 访问出现New XAMPP security concept 解决办法
  5. 通过xib创建View
  6. .net中运用solr提升搜索效率(入门)
  7. tomcat发布web service教程
  8. spring 学习 AOP和IOC
  9. 使用pymysql和paramiko实现远程安装软件
  10. VSTO之旅系列(四):创建Word解决方案
  11. ITIL该研究的结论(互联网思维的结合)
  12. mongoDB &amp; Nodejs 访问mongoDB (一)
  13. HTML canvas绘制椭圆
  14. C语言pow()函数的计算精度问题
  15. WIN10远程连接,报错身份验证错误,要求的函数不受支持
  16. 【nginx&amp;php】后台权限认证方式
  17. 适配ipad Pro
  18. error: The function/feature is not implemented (Odd-size DCT&#39;s are not implemented)in function cvDCT.
  19. Linux配置Selenium+Chrome+Java实现自动化测试
  20. MySQL找出锁等待