// N*M算法
// KMP算法,这里是学习刘汝佳大神书上的代码class Solution {
// public int strStr(String haystack, String needle){
//if (needle == null || needle.length() == 0)return 0;
//if (haystack == null || haystack.length() == 0) return -1;
//if (haystack.length() < needle.length()) return -1;
//boolean flag = false;
//for (int i = 0;
i < haystack.length() - needle.length() + 1;
i++){
//flag = false;
//for (int j = 0, index = i;
j < needle.length();
j++,index++){
//if (haystack.charAt(index) != needle.charAt(j)){
//flag = true;
//}
//}
//if (!flag)
//return i;
//}
//return -1;
// }public int strStr(String haystack, String needle){
if (needle == null || needle.length() == 0)return 0;
if (haystack == null || haystack.length() == 0) return -1;
if (haystack.length() < needle.length()) return -1;
int[] f = new int[needle.length() + 1];
getFail(needle, f);
int n = haystack.length();
int m = needle.length();
int j = 0;
for (int i = 0;
i < n;
i ++){
while(j != 0 && haystack.charAt(i) != needle.charAt(j))
j = f[j];
if (haystack.charAt(i) == needle.charAt(j)) j++;
if (j == m) return i - m + 1;
}
return -1;
}public void getFail(String P, int[] f){
int m = P.length();
f[0] = 0;
f[1] = 0;
for (int i = 1;
i < m;
i++){
int j = f[i];
while (j != 0 && P.charAt(i) != P.charAt(j))
j = f[j];
f[i + 1] = P.charAt(i) == P.charAt(j) ? j + 1 : 0;
}
}
}【LeetCode|LeetCode 28 实现strStr() 字符串匹配KMP】
推荐阅读
- Java|Java基础——数组
- 人工智能|干货！人体姿态估计与运动预测
- java简介|Java是什么（Java能用来干什么？）
- Java|规范的打印日志
- Linux|109 个实用 shell 脚本
- 程序员|【高级Java架构师系统学习】毕业一年萌新的Java大厂面经，最新整理
- Spring注解驱动第十讲--@Autowired使用
- SqlServer|sql server的UPDLOCK、HOLDLOCK试验
- jvm|【JVM】JVM08(java内存模型解析[JMM])
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)