本文记录kmp算法的思路，并练习编写github的README文件。
本仓库包含以下内容：
- kmp算法代码。
- REAME文档中引用的素材。
在已经匹配的前缀当中寻找到最长的可匹配后缀子串以及最长的可匹配前缀子串，以此省略无效的匹配，从而在下一轮直接将子串的前缀与字符串的当前位置对齐，从而实现模式串的快速移动。 总的时间复杂度为o(n)。
为了实现算法思路，需要一个一维数组，用来存放子串每个位置的最长可匹配前缀的后一个位置。
上图中的cn指示i-1位置的最大匹配前缀的下一个位置。特别设置next[0]=-1,next[1]=1。
-
- v[cn]==v[i-1]
如果v[cn]等于v[i-1]，因为v[i-1]的前后缀已经是最长，所以各自加上v[cn]与v[i-1]就是v[i]的最长匹配前后缀。
next[i] = next[i-1]+1;
-
- v[cn]!=v[i-1]
如果v[cn]不等于v[i-1]，因为v[i-1]的匹配前后缀已经最长，所以包含v[i-1]的匹配前后缀不会更长，于是指示点cn要往前查找，直到找到v[cn]等于v[i-1]的前后缀。
cn = next[cn];
-
- next[cn]==-1
如果v[cn]与v[i-1]一直不匹配，那么cn最后会来到数组下标为0的位置，说明v[i]没有匹配的前后缀，只能从主串的下一个位置开始重新判断匹配。
得到next数组后，就可以开始字符串的匹配过程了。使用两个整数保存主串与子串的下标。如果对应位置的字符相同，两个下标自增；如果对应位置的字符不同，根据子串的next数组，调整子串的下标。经过这一调整就可以跳过无效对比的过程。