代码随想录打卡第9天 | KMP算法

进行一下字符串总结

　　1, 双指针的灵活运用, 删除元素 倒转链表 (后序添加元素, 如果是从前往后添加, 每次添加元素都要将之后的元素后移 o(n*2)的复杂度 )

　　2, 反转法: 先整体反转再局部反转，实现了反转字符串里的单词。

　　3, KMP算法

a: 0 只有一个字符，为0
aa: 1 前缀为a 后缀为a 相等，最长相等前后缀为1
aab :0 前缀为a、aa； 后缀为b、ab，最长相等前后缀长度为0
aaba: 1 前a、aa、aab；后a、ba、aba，最长相等前后缀长度为1
aabaa: 2 前a、aa、aab、aaba；后a、aa、baa、abaa，最长相等前后缀长度为2
aabaaf: 0 前a、aa、aab、aaba、aabaa；后f、af、aaf、baaf、abaaf，最长相等前后缀长度为0
　void getNext(int[] next, String s){
　　int j=0;
　　next[0]=0;
　　
　　for(int i = 1; i<s.length(); i++{
　　　　while(j>0&&s.charAt(i)!=s.charAt(j)
　　　　　　j=next[j-1];  // 这一步是为了找到具有最大相等前后缀的位置
　　　　if(s.charAt(i)==s.charAt(j)
　　　　　　j++;
　　　　next[i]=j;
}
}

　　4, length()是求String字符串对象中字符的个数，而length是求字符串数组中有多少个字符串。size()方法，是List集合的一个方法；