Java Web总结

————————下面是废话,可以不看————————

好久都没有写博客了,搞定了Android和Linux实验报告后暂时可以稍微闲下来几天。这次我们来聊聊关于网站的一些故事,我大概从今年4月开始搭建校内中央认证系统(CAS),为的是集成社团内所有开源系统的登录过程,达到单点登录的效果。什么意思呢?就是像在网上一些站点见到的那样,可以通过其他方式登录,比如通过QQ登录,通过新浪微博登录什么的。

这个系统是基于Java Web实现的,支持多种认证协议和多语言版本的客户端,方便和其他系统做对接和集成。github地址:https://www.apereo.org/projects/cas  校内使用的版本是4.2.0,地址为https://cas.bistu.edu.cn

当然这次我并不是想聊CAS的,Java Web的课程已经接近了尾声,这个系列文章主要是总结下Java Web相关的一些东西。

————————上面是废话,可以不看————————

首先呢,我要慢慢介绍一些相关的技术,主要讲解动态网站的来龙去脉。。对,故事开始。

1.浏览器、网页、HTML

如果你学过Java,那么你肯定知道Java可以使用swing、JavaFX技术编写图形界面程序。

如果你学过C++ ,那么你肯定知道可以使用一些图形库或者win32的API来编写图形界面。

现在,有这么一种东西,不需要编译,不需要很长时间的学习就可以做出一个看得见的界面。就是HTML。

上面的这段内容就是一个最简单的HTML框架,把上面的内容复制到一个文件中,文件名改为xxx.html,用浏览器打开你就看到这样的效果。

(这里应该有张图,但是并没有23333自己试试是什么效果吧)

这样显示出来的界面就是一个HTML页面,也叫一个网页。把这个文件打开的程序就是浏览器。常见的浏览器有IE、Chrome、火狐等。你会发现,如果你用编辑器打开html文件,看到的就是纯文本,而浏览器可以把它显示成一个界面。浏览器的任务之一就是读取html文件中的内容,并把它显示成正常人能看懂的效果,记住浏览器的这个任务,之后还会有用。

2.CSS

css的翻译是层叠样式表,说的简单点就是负责描述html中元素的样式,比如颜色、边距啥的。大概长这样

选择器可以控制这些样式适用于什么元素,可以按标签名选取、按类选取等。。。不啰嗦了,总之就是这样。

3.Javascript

Javascript是一种脚本语言,由浏览器负责执行,这是浏览器的任务2。脚本的意思可以简单理解为一行行的执行。如果浏览器见到了<script>标签,就会去解析里面的js代码。如果这个标签在body中,当加载到脚本的时候会立即执行。

上面所说的内容都可以在任意网页按F12打开开发人员工具进行尝试。在开发工具部分可以看到当前页面所有html源文本,以及可以选择任意元素查看生效的css样式,并且可以在控制台指定js代码进行调试。

到此为止,前端基础技术就介绍完了。这些并不是本次的重点。

4.Web服务器

如果你照着上面说的做了,你会发现打开后地址栏显示的地址是file://开头的。这说明这个文件是存储在你的本地计算机中。而平时打开的网页开头都是http开头,怎么做到呢?你需要一个Web 服务器。

刚刚我们说过了,浏览器看到html文本就能显示成网页,如果html文本是从远程电脑发来的呢?浏览器可以通过http协议和远程服务器进行通讯,交换传输html文本。服务器你可以理解为一个远程的电脑,上面运行着一个特殊的程序,这个程序的任务是等待浏览器发送的http请求,找到浏览器想访问的html文件,然后把内容发给浏览器。这个特殊的程序就是Web服务器软件,运行着这种软件的服务器就可以叫Web服务器,有的时候Web服务器指的就是Web服务器软件,要看上下文语义来理解。常见的Web服务器软件有Apache、Nginx、Tomcat等。他们的作用是相似的。

1

在这里又要请出F12的开发工具了,点击网络标签开始监听后,可以看到浏览器发出的所有网络请求,点击请求可以看到请求的header、服务器回应的内容等信息,借助这个可以来看当前的请求是不是你想要的请求。

5.动态网站vs静态网站

很多的html页面通过超链接连起来后,就是一个简单的静态网站了。静态网站简单的来说就是不会动的网站,比如刚刚写的那个demo,无论请求多少次,内容都不会发生任何变化。即使你放入了Flash、gif等看起来“动”了的元素进去,也依然不是动态,因为服务器返回的html文本没有发生任何变化。

那么,如果服务器返回的结果不是直接从html文件取得的,而是服务器上另一个程序的执行结果,那么每次的结果就取决于这个程序的逻辑了。这样做出的网站就可以是动态网站,比如最简单的显示当前访问总次数的页面。

常见的动态网站有PHP、Java、Python等,需要的环境也各不相同,但是本质都是一样的,只要有程序能运行并生成结果是html格式,就可以实现动态网站。

 

6.Java Web

扯了这么多终于能回到正题了,Java号称跨平台是因为字节码的存在,不同的操作系统有不同的Java虚拟机来执行同样的字节码,也就是class文件。用Java做动态网站也就是要执行Java代码,负责执行Java代码并把结果返回给浏览器的程序就是Tomcat。

—————题外话—————

在实际的网站中,一般并不把Tomcat的8080端口直接暴露,而是通过nginx或者Apache反向代理访问。用户浏览器请求的依然是80端口,由反向代理再向Tomcat发出请求。效果如http://tomcat.hylstudio.cn。Apache配置如下:

—————题外话—————

7.Jsp、Servlet

如果把请求转发给Servlet,那么对应的Java代码就会被执行。带来的问题是:在Java代码中拼接html文本十分恶心,大概这样。

所以,我们设想,如果不自己写out.println让程序自动补上口不口以?当然口以,这就是jsp。在jsp里出现的html标签会自动转换成上面这样的代码,而出现在<%%>中间的内容不会加上out.println。这样就结束了么?显然没有,人们发现虽然jsp写界面很方便,但是写代码逻辑非常恶心,如果有多个ifelse套起来根本不是人看的玩意。

所以,一般来说,我们用jsp只负责显示,用Servlet负责处理业务逻辑,也就是MVC。整体思路是这样的,用户的请求只由Controller层的Servlet处理分发、View层的jsp负责显示、所有的数据都有Model层的JavaBean封装。这样分工后,Servlet和jsp各自的优势都发挥了出来。

8.套路

分层后可以发现,每层做的工作非常的单一并且规律性极强。人们再次做了抽象,把相同的部分写好,把需要变化的东西用xml表示,也就是用xml来填充一个Java代码中没写完的部分。这样就有了框架,比如常见的Spring。

同理在数据处理上也有套路,也就是DAO模式,定义负责数据访问的接口。好处是通过调用统一的接口来进行屏蔽掉数据访问的具体实现(不然我怎么可能把xml的实验代码用了四次23333)。

 

9.其他资料

本文并没有详细介绍每一个细节,其中提到的做法可能需要用到的知识如下。

正则表达式:http://deerchao.net/tutorials/regex/regex.htm

bootstrap的套用:http://v3.bootcss.com/getting-started/

spring框架的使用:http://spring.io/guides

CSS参考:http://www.runoob.com/css/css-intro.html

一个好玩的C语言程序

 

Linux笔记1(Linux运维、大数据相关工具)

Linux下好用的软件

智能终端fish:

http://fishshell.com/docs/current/index.html#introduction

多人协作、不间断运行的shell:tmux

https://tmux.github.io/

http://man.openbsd.org/OpenBSD-current/man1/tmux.1

 

http://blog.jobbole.com/87584/

 

自动化运维ansible

http://docs.ansible.com/

http://sofar.blog.51cto.com/353572/1579894/

 

多虚拟py环境vituralenv

http://www.liaoxuefeng.com/wiki/0014316089557264a6b348958f449949df42a6d3a2e542c000/001432712108300322c61f256c74803b43bfd65c6f8d0d0000

http://www.cnblogs.com/tk091/p/3700013.html

 

py包管理 pip

https://pypi.python.org/pypi/pip/

http://www.ttlsa.com/python/how-to-install-and-use-pip-ttlsa/

 

开源大数据工具luigi

http://luigi.readthedocs.io/en/stable/

http://www.oschina.net/p/luigi

http://www.open-open.com/lib/view/open1413337781090.html

 

【资源导航】

欢迎来到我的博客。

预告:最近即将更新的内容=-=

Skykoma系列

云端开发环境 https://github.com/dev-assistant/skykoma-workspace

IDE自动化 https://github.com/dev-assistant/skykoma-plugin-idea

服务器搭建系列

录屏 https://space.bilibili.com/7757632/channel/collectiondetail?sid=3917759&ctype=0

文章 https://blog.hylstudio.cn/archives/category/fuwuqi

MDSE实践计划系列

尝试完成部分半自动化的开发流程,部分可投入生产

20210828.近期动态分享:MDSE实践计划及过程记录

20211023.Web后端参数检查的通用代码生成设计与实现

其他已填flag

1.数据结构 https://github.com/956237586/DataStructure-C
2.从零实现Web服务器:包含从Socket层实现部分HTTP协议,手动实现模板引擎、路由等功能。视频已发布,仅作原理性说明,未做工程化重构 https://www.bilibili.com/video/BV18h41147b8/
3.C语言教程

C语言系列基础教程(传统讲法) http://blog.hylstudio.cn/archives/174

2020年版本(井字棋) https://blog.hylstudio.cn/archives/746

数据结构——基础测试

 

数据结构基础


前言

数据结构主要要解决的问题是:

  1. 数据如何在内存中存储,以什么结构存储。
  2. 对应不同的存储结构应该用什么样的方法对数据进行操作来满足相应的需求。

简单来说,上面第一点就是数据结构,第二点就是算法。不同的数据结构必然会有不同的算法来对数据进行操作。

学习需要的基础

  1. 任意一种编程语言基础。(比如C语言
  2. 熟悉理解内存的结构并能精确控制。(比如利用C的指针正确控制内存
  3. 面向对象的编程思想。

基础测试

阅读下面的代码,回答后面的问题,如果你都能和答案理解意思一样,说明:

  1. 你C语言基础已经可以学习数据结构并且不会有什么大问题。
  2. 你对内存结构有了深刻的理解。
  3. 你有了基本的面向对象思想,以及明白了面向对象在底层的部分实质。

代码如下:

问题:

  1. 第9行的目的是什么?
  2. newStudent的意义是什么,它的返回值类型为什么是Student?
  3. Student的本质是什么?
  4. 21行写成Student stu1;同时删掉22行行不行?
  5. 23行、28行为什么要用->,能不能用.(这是一个点)

答案解析将在之后更新。。。如果你无法回答,可以阅读思维导图指针教程部分的内容

答案

  1. 第9行的目的是把一组数据集合的指针定义为一种新的类型。
  2. newStudent的意义是创建新的学生,返回值是指向学生的指针。
  3. Student的本质是结构体的指针。
  4. 不行,仅有指针并没有申请内存,数据实际还不存在。
  5. 因为是结构体的指针,而不是结构体本身,所以用->访问。

内存分析

第15行
调用newStudent函数,传入参数。
申请1块内存stu1,把函数返回值赋值给stu1。

第20行:函数调用内部
申请一个结构体指针ret初始化为空。
用malloc动态申请一个结构体大小的内存,并把首地址赋给ret。
利用传入的参数初始化结构体的内容。
把ret里面的内容返回,ret在函数结束后被自动回收。

回到16行
把stu1的内容传入show函数。

第27行:函数调用内部
根据传入的stu访问里面的数据。

回到17行程序结束。

内存图解

15行函数调用前

mxdxjc1

函数调用过程,21行开始执行

mxdxjc2

21行执行完毕,开始执行22行

mxdxjc3

mxdxjc4

22行执行完毕,开始执行23行

mxdxjc5

23行执行完毕,返回15行,传回ret

mxdxjc6

开始执行16行

mxdxjc7

28-30行开始执行,根据this指针访问内存。函数结束,回收show函数空间。

mxdxjc8

 

总结

看到this是不是很熟悉??面向对象其实就是对一个数据集做一些操作,这些数据就叫属性,这些操作就叫方法。改改语法是不是和Java或者C++很相似??这些既是面向对象的底层部分细节,也是学习数据结构必要的知识,只有对内存了如指掌才有可能灵活的控制使用内存。

2015.11.6.KMP算法

 

       KMP算法是要解决的问题是一个字符串中查找指定子串的问题。由于臻臻问我这个问题,所以我不得不再次看看KMP -_-|| ,同时感谢袁涛和王宇晖Orz,(另:默默等待王霸的KMP第三层优化,但愿他能成功)。

       本人水平不高,有写错的地方还请批评指正。

       先说传统的匹配算法。以图中的字符串为例,第一行是要匹配的目标字符串(称之为主串。其中第i个简写为S[i]),要匹配的字符串称之为子串(也叫模式串,其中第i个简写为P[i])接下来每行代表一次匹配操作,黄色部分代表匹配成功的部分,红色字符为发现的第一个不匹配的字符。所有字符计数从1开始。所有字符计数从1开始。所有字符计数从1开始。(重要的事情说三遍)

 

左侧第一列是每一次匹配情况。下面是详细的匹配过程描述。为了方便观察变化,上图中每次移动子串将在新行展现。实际匹配时只在当前行向后移动。

1.P[1]和S[1]对齐。

2. 比较S[1]与P[1]是否相同结果是不相同)。图中第1行

3. 将P[1]和S[2]对齐(把模式串向后移动1个字符的位置)。

4. 比较P[1]与S[2]是否相同(结果是相同)。

5. 比较P[2]与S[3]是否相同(结果是相同)。

6. 比较P[3]与S[4]是否相同(结果是相同)。

7. 比较P[4]与S[5]是否相同(结果是不相同)。图中第2行

8. 将P[1]和S[3]对齐(把模式串向后移动1个字符的位置)。

9. 比较P[1]与S[3]是否相同(结果是不相同)。图中第3

10. 将P[1]和S[4]对齐(把模式串向后移动1个字符的位置)。

11. 比较P[1]与S[4]是否相同(结果是不相同)。图中第4

12. 将P[1]和S[5]对齐(把模式串向后移动1个字符的位置)。

13. 比较P[1]与S[5]是否相同(结果是不相同)。图中第5

14. 将P[1]和S[6]对齐(把模式串向后移动1个字符的位置)。

15. 比较P[1]与S[6]是否相同(结果是相同)。

16. 比较P[2]与S[7]是否相同(结果是相同)。

17. 比较P[3]与S[8]是否相同(结果是相同)。

18. 比较P[4]与S[9]是否相同(结果是相同)。

19. 比较P[5]与S[10]是否相同(结果是相同)。

20. 比较P[6]与S[11]是否相同(结果是相同)。

21. 比较P[7]与S[12]是否相同(结果是相同)。

22. 比较P[8]与S[13]是否相同(结果是不相同)。图中第6

23. 将P[1]和S[7]对齐(把模式串向后移动1个字符的位置)。

24. 比较P[1]与S[7]是否相同(结果是不相同)。图中第7

25. 将P[1]和S[8]对齐(把模式串向后移动1个字符的位置)。

26. 比较P[1]与S[8]是否相同(结果是不相同)。图中第8行

27. 将P[1]和S[9]对齐(把模式串向后移动1个字符的位置)。

28. 比较P[1]与S[9]是否相同(结果是相同)。

29. 比较P[2]与S[10]是否相同(结果是相同)。

30. 比较P[3]与S[11]是否相同(结果是相同)。

31. 比较P[4]与S[12]是否相同(结果是相同)。

32. 比较P[5]与S[13]是否相同(结果是不相同)。图中第9

33. 将P[1]和S[10]对齐(把模式串向后移动1个字符的位置)。

34. 比较P[1]与S[10]是否相同(结果是不相同)。图中第10行

35. 将P[1]和S[11]对齐(把模式串向后移动1个字符的位置)。

36. 比较P[1]与S[11]是否相同(结果是不相同)。图中第11

37. 将P[1]和S[12]对齐(把模式串向后移动1个字符的位置)。

38. 比较P[1]与S[12]是否相同(结果是相同)。

39. 比较P[2]与S[13]是否相同(结果是不相同)。图中第12

40. 将P[1]和S[13]对齐(把模式串向后移动1个字符的位置)。

41. 比较P[1]与S[13]是否相同(结果是相同)。

42. 比较P[2]与S[14]是否相同(结果是相同)。

43. 比较P[3]与S[15]是否相同(结果是相同)。

44. 比较P[4]与S[16]是否相同(结果是相同)。

45. 比较P[5]与S[17]是否相同(结果是相同)

46. 比较P[6]与S[18]是否相同(结果是相同)

47. 比较P[7]与S[19]是否相同(结果是相同)

48. 比较P[8]与S[20]是否相同(结果是不相同图中第13

49. 将P[1]和S[14]对齐(把模式串向后移动1个字符的位置)。

50. 比较P[1]与S[14]是否相同(结果是不相同)。图中第14

51. 将P[1]和S[15]对齐(把模式串向后移动1个字符的位置)。

52. 比较P[1]与S[15]是否相同(结果是不相同)。图中第15

53. 将P[1]和S[16]对齐(把模式串向后移动1个字符的位置)。

54. 比较P[1]与S[16]是否相同(结果是相同)。

55. 比较P[2]与S[17]是否相同(结果是相同)。

56. 比较P[3]与S[18]是否相同(结果是相同)。

57. 比较P[4]与S[19]是否相同(结果是相同)。

58. 比较P[5]与S[20]是否相同(结果是相同)

59. 比较P[6]与S[21]是否相同(结果是相同)

60. 比较P[7]与S[22]是否相同(结果是相同)

61. 比较P[8]与S[23]是否相同(结果是相同)

62. 比较P[9]与S[24]是否相同(结果是相同)

63. 比较P[10]与S[25]是否相同(结果是相同)

64. 匹配成功。图中第16行

 

仔细观察原始匹配算法的规律,以上述第15步开始为例。

模式串的前7个字符P[1 2 3 4 5 6 7]与主串S中的某个子部S[6 7 8 9 10 11 12]相匹配时,如果P[8](图中红色的c)S[13](a)匹配失败,下一次将会把P[1]S[7]对齐,然后从P[1]与S[7]开始向后逐一进行匹配。

也就是说:

当模式串的前i个字符P[1 – i]与主串S中的某个子部S[m ···· m + (i – 1)]相匹配时,如果P[i + 1](图中红色的c)S[m + i](a)匹配失败,下一次将会把P[1]S[m + 1]对齐,然后从P[1]与S[m + 1]开始向后逐一进行匹配。

至此原始的字符串匹配算法结束。

 

我们最开始的目的是找到主串S中是否存在子串P,也就是说我们希望尽可能多的匹配子串P的内容。观察图中第6-9行的过程(对应上文步骤14开始的过程)。

 

当P[8](图中红色的c)S[13](a)匹配失败,会有两次后移子串的操作,这时会发现在第9行中子串P的前4个字符组成的字符串和第6行中前7个字符组成的子串的后4个字符组成的字符串是一样的。也就是图中蓝色框线部分。放到一起来看是这样的:

换句话说,也就是子串前7个字符组成的字符串的头部和尾部有4个字符匹配(下文称之为前缀和后缀)。

这时观察上面的图,那么可以思考一个改进方案,就是当发现P[8]与S[13]不匹配的时候,下一步直接比较P[5]和S[13](因为前4个已经在图中第6行匹配过了),也就是把子串S移动了3个字符的距离

在这里我们引入跳转表如下(先不要管怎么算的)

含义是:当P[j]与主串中某个字符(设为t,在上例中是S[13]不匹配时,从P[next[j]](P[5])开始继续与主串中的t(S[13])比较(也就是把子串后移j next[j]个字符的距离),例如上例中的next[8] = 5,含义就是当P[8]与t(S[13])匹配不成功时,直接从P[5]开始继续与主串中的t(S[13])比较(也就是把子串后移8-5个字符的距离)。

可以发现,next的数值是和主串无关的,只和这个子串本身有关。那么这样,最原始的匹配步骤就可以变成下面图中的样子。也就是每次尽可能多的匹配子串与主串,不要每次都移动一个进行尝试。

 

那么问题来了(不是蓝翔),怎么计算next[j]?

根据前面的例子可以看出,next[j]的值就是P[1 ····· j – 1]中可以找到的最长且相等的前缀与后缀的长度再加1(规定第1个值为0,因为如果第一个字母都不匹配的话就要向后移动1个字符的长度,1 = j – next[j] = 1 – 0),比如前面例子中子串前7个字符中可以找到最长且相等的前缀和后缀就是abca,长度是4,所以next[8]的值就是4 + 1 = 5。按照这个原则,就可以构造出上面的跳转表了。

上面的方法是人眼非常方便的做法,但是如果要写程序则会变得非常复杂。并且当字符串变长或者字的数量变多的时候直接查找会变的非常低效。所以需要考虑程序怎么方便快速的实现,在这种时候通常的思路是充分利用之前的结果。

例如想求next[5],假设next[4]以及以前的next值都已经计算完毕如图。

想求next[5],也就是模式串前4个字符中能找到最长的一对前后缀长度+1, 这时我们已知next[4] = 1也就是说模式串前3个字符找不到一对前后缀相等,我们尝试考虑加上第4个字符P[4]看看能不能找到,既然已经知道前3个中找不到一对相等的前后缀,那么只需要判断要加入的字符P[4]和P[1]是不是相同,如果相同,那么代表加入P[4]后最长前后缀的长度可以增加1,也就是next[5] = next[4] + 1 = 1 + 1 = 2

另外一个例子

       想求next[8],假设next[7]以及之前的值已知如图。

想求next[8],也就是模式串前7个字符中能找到最长的一对前后缀长度+1, 这时我们已知next[7] = 4也就是说模式串前6个字符找到最长且相等的一对前后缀长度为3(图中红色和蓝色部分),我们尝试考虑加上第7个字符P[7]看看能不能延长最长前后缀的长度,既然已经知道前6个中找到最且相等的一对前后缀长度为3,那么只需要判断要加入的字符P[7]与P[4]是不是相同(红框后的红圈字符和篮框后的红圈字符),如果相同,那么代表加入P[7]后最长前后缀的长度可以增加1,也就是可以延长也就是next[8] = next[7] + 1 = 4 + 1 = 5

       分析上面的过程,其实就是尝试尽可能添加进更多的字符进入已经找到的最长且相等的前后缀中,第一个字符的next值一定是0,从第二个开始使用上面的规律,如果最后一个字符的加入可以延长最长前后缀,那么就加进去,如果之前已经没有最长的前后缀,那么直接写1。

       再找一个特殊情况如下(为了说明另一种情况我换了个字符串)。想求next[5]

想求next[5],也就是模式串前4个字符中能找到最长的一对前后缀长度+1, 这时我们已知next[4] = 2也就是说模式串前3个字符找到最长且相等的一对前后缀长度为1(图中红色和蓝色部分),我们尝试考虑加上第4个字符P[4]看看能不能延长最长前后缀的长度,既然已经知道前3个中找到最且相等的一对前后缀长度为1,那么只需要判断要加入的字符P[4]与P[2]是不是相同(红框后的红圈字符和篮框后的红圈字符),如果相同,那么代表加入P[4]后最长前后缀的长度可以增加1,但是显然P[4]与P[2]不等,加入后无法延长目前最长前后缀的长度。这时候却不能结束,因为你明显能看到前4个字符最长的前后缀长度明明是1,所以要继续尝试将P[4]与P[1]比较,如果相同,那么说明最长前后缀长度可以从0增加到1,所以next[5] = next[2] + 1 = 1 + 1 = 2

说了这么多,求next[j]方法推导总结如下:

next[1] = 0 (j = 1)

假设next[j] = k,求next[j + 1]。

next[j] = k (由假设),所以有:

P[1 ···· (k – 1)] = P[( j – (k – 1)) ···· (j – 2) (j – 1)] (由定义)

分两种情况讨论:

P[k]=P[j],则有P[1 ···· (k-1) k] = P[ (j – (k – 1)) (j – (k – 2)) ···· (j -1)  j ],且不存在k’ > k 满足等式

(图中取j = 7的情况)

所以,next[j + 1] = k + 1=next[j] + 1

P[k] P[j]( k < j ),则将求next函数值的问题看成一个模式匹配问题,整个模式串既是主串又是模式串。(图中取j=8的情况)

 

继续设已知next[k] = k’(也就是图中的next[5] = 2)

分两种情况讨论:

P[k’] = P[j],则有P[1 2 ···· (k’ – 1) k’] = P[(j – (k’ – 1)) (j – (k’ – 2)) ···· (j – 1) j ] (1 < k’ < k < j )

那么next[j + 1] = k’ + 1 = next[k] + 1

P[k’] P[j] ( k < j ),则又将求next函数值的问题看成一个模式匹配问题,整个模式串既是主串又是模式串

 

重复以上讨论:直至P[j]和模式串中某个字符匹配成功,即找到某个k’’使next[j + 1]=k’’ + 1=next[k’] + 1

反之不存在任何k*(1 < k* < j),则next[j + 1] = 1。

     

到此为止,搜索的过程就可以优化成上图的样子了。但是还没完,仔细看,第2次匹配,当发现P[4](a)与S[5](b)匹配失败时,下一次匹配按照跳转表应该是P[1]继续和S[5]匹配,但是可以发现P[4]和P[1]是一样的,那么进行两次匹配是没必要的,所以我们就可以再进行一次优化。第9行的情况也同理。

可以简化成下图这样。对应跳转表也在下面。

在第一次的跳转表的基础上,如果发现要跳转的字符和自身相等,那么可以把自身的next值改为要跳转字符的next值,否则保持不变,计算过程中依然充分利用已知的nextval值。举几个例子:

·······

上图中的next[2] = 1,而P[2] ≠ P[1],所以nextval[2] = next[2] = 1。

·······

上图中的next[4] = 1,而P[4] = P[1],所以nextval[4] = nextval[1] = 0。

上图中的next[6] = 3,而P[6] = P[3],所以nextval[6] = nextval[3] = 1。

上图中的next[10] = 2,而P[10] = P[2],所以nextval[10] = nextval[2] = 1。

 

经过这两次优化,可以发现,原本需要匹配16次的事情现在只需要匹配6次即可完成。是不是非常神奇?