KMP算法的个人理解
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
这个就是最经典的kmp题目，两个字符串，求第一个匹配项。
正常的想法都是双指针。从左到右一个个匹配，如果这个过程中有某个字符不匹配，第一个指针会到原位置，第二个指针移到第0位。
上面的程序是没有问题的，但不够好！
如果是人为来寻找的话，肯定不会再把i移动回第1位，因为主串匹配失败的位置前面除了第一个A之外再也没有A了，我们为什么能知道主串前面只有一个A？因为我们已经知道前面三个字符都是匹配的！（这很重要）。移动过去肯定也是不匹配的！有一个想法，i可以不动，我们只需要移动j即可
原文链接：https://blog.csdn.net/weixin_52622200/article/details/110563434
思路其实也很简单，我们的双指针算法问题在于，每次第一个指针都要回到原来的位置，那能不能第一个指针不动，当第一个指针与第二个指针指向的字符不一致的时候，第二个指针动。
i
ABABABCAA
ABABC
k
当i和k指针指向的数据不一致时候，i不要变为2，而是k变成2.
i
ABABABCAA
ABABC
k
这样我们就可以继续对比下去了，只要k什么时候变成第二个字符串的长度，就说明中了。
为什么能这么变呢。
我们把ABABC分为两部分，可以知道ABAB和C。 我们在匹配到C的时候，我们一定知道第一个字符串形式应该是
XX ABABX MM
我们已知的信息就说这段是ABAB的，那我们第二字符串就可以从第二开始对比，为什么，因为第二字符串的头AB和第一个字符串的AB相同，换句话说，就说ABAB的前后共同部分长度为2.
那么我们只要知道第二个字符串每个长度的共同最大长度数据next[]就可以了。
后面他们说的就很清楚了，就是当求解next算法的时候，他们的写法看起来很优美，但是我写不出来，理解不了啊。
那怎么办呢。看了b站的动画视频后，我就理解了。
我们求解下ABACABAB的next数组。
我们自然就想到从头开始。A 那自然是0，那AB呢，我们人眼看出来也是0，但是机器不知道啊，难道我们要头尾指针，再算一遍吗，可以是可以，但是不应该啊，每个长度都头尾一下，也很麻烦啊。
我们自然就想到，第一步是不是包含了第二步的信息。
现在暂时看不出来，那继续。
ABA 1
ABAC 0
ABACA 1
ABACAB 2
这里就有点感觉了，为什么ABACAB是2，我们人知道，因为ABACA是1，所以我们只要比较ABACA的第二个位置B和我们最后的ABACAB的B是否一致。是的话，我们就是1+1.
这里我们就可以知道，如果字符串的next[i-1位置的字符串和i位置一致，那么next[i]=next[i-1]+1；
但是如果不一致的话， 我们该怎么处理呢。
我们继续下去，
ABACABA 3
ABA |C ABA |B 这个我们是怎么算的呢C与B不一致，那么是要从头算吗。
不一定哦
我们知道ABACABA 是3 那么说明里面有一段是共同的，就是ABA|C|ABA
那我们ABA这段呢，A|B|A
右边的后缀=左边的后缀，同事左边的一部分后缀=左边的一部分前缀，所以，应该存在一个左边的前缀=右边某一部分后缀。那么自然A|BACAAB|A ,那么这个时候，就检查，第一个A的下一个B是不是跟最后的B相同，如果相同就是1+1.如果不同那再去更小的前缀相同的进行比较。
public static int strStr(String haystack, String needle) {if(needle==null || needle.length()==0) return 0;if(haystack==null || needle.length()==0) return -1;int alength = haystack.length();int blength=needle.length();char[] haystackA = haystack.toCharArray();char[] needleA = needle.toCharArray();int[] next = getnext(needle);int posA=0;int posB=0;while(posA<alength){if(haystackA[posA]==needleA[posB]){posA++;posB++;}else if(posB>0){posB=next[posB-1];}else{posA++;}if(posB==blength){return posA-posB;}}return -1;}public static int[] getnext(String target) {int length = target.length();int[] next = new int[length];int i=1;int prefix_len=0;while(i<length){if(target.charAt(prefix_len)==target.charAt(i)){prefix_len=prefix_len+1;next[i]=prefix_len;i++;}else{if(prefix_len==0){next[i]=0;i++;}else{prefix_len=next[prefix_len-1];}}}return next;}那些算法为什么看起来这么优美，简单高效。因为是经过了优化的。但是缺点就是因此失去了语义。
