声明
博客中关于算法截图,来自七月算法PPT,bilibili地址 博文涉及代码地址:码云
原题
解题思路
暴力法
public int strStr(String haystack, String needle) {
if (needle.length() == 0) {
return 0;
}
int needStart = 0;
//for 循环每个位置开始匹配
for (int i = 0; i + needStart < haystack.length(); i++) {
//从首位开始比较
while (i + needStart < haystack.length() && needStart < needle.length()) {
if (haystack.charAt(i + needStart) == needle.charAt(needStart)) {
//匹配,则比较位置向后一位
needStart++;
} else {
//不匹配,比较位置归零,跳出循环,i向后移动一位
needStart = 0;
break;
}
}
//如果比较位置超过了,匹配字符长度,则是已经匹配到
if (needStart >= needle.length()) {
return i;
}
}
//没有匹配到返回-1
return -1;
}
KMP算法
算法说明
- kmb算法解释
- kmb核心算法 next() 看完想法:next()函数作用,就是求前缀和后缀是否重复部分,有重复的时候,在平移的时候要考虑
算法实现
xxxxxxxxxx
/**
* @param haystack 源字符串
* @param needle 匹配字符串
* @return int
* @throws
* @author Eric
* @date 2019/5/22
**/
public int kmpStrStr(String haystack, String needle) {
if (needle.length() == 0) {
return 0;
}
int[] next=next(needle);
int p=0;
int i=0;
while(i<haystack.length()){
if(p == -1||haystack.charAt(i)==needle.charAt(p)){
++p;
++i;
}else{
p=next[p];
}
if(p>=needle.length()){
return i-p;
}
}
return -1;
}
/**
* <p>
* 求出 匹配字符串得next函数
* 0 j=0
* next()= Max{k|0<k<j , P1 P2 ...Pk=Pj-k+1 Pj-k+2}
* 1 其他情况
* </p>
*
* @param needle 1
* @return int[]
* @throws
* @author Eric
* @date 2019/5/22
**/
public int[] next(String needle) {
int[] arr = new int[needle.length()+1];
arr[0]=-1;
for (int i = 0; i < needle.length(); i++) {
int k=i;
if ( i== 0) {
arr[i+1] = 0;
} else if (0 < k && k <= i) {
while (k > 0) {
if (needle.substring(0, k).equals(needle.substring(i+1 - k , i+1))) {
arr[i+1] = k;
break;
}
k--;
}
}
}
return arr;
}
总结: 结果并不是太理想,我都不好意思贴leetcode运行结果了,消耗的空间和时间都非常的多,空间消耗比较多,主要再subString()方法会重复new对象,这里可以优化,但是就算我优化了,也是需要遍历,时间复杂度又提升 疑问:KMP真的有那么优秀,再我看来,KMP真的不如BF算法,假设没有不考虑求next数组的时间复杂度,KMP确实M+N的复杂度,但是求next数组应该是M*M(非专业,大概计算,不会推到)级别的 最后求大佬指点,哪里不对,哪里还有可以优化
自己优化next函数
- 不使用substring方法,自己写方法实现同样的效果,结果空间复杂度确实降下来了,时间复杂度依旧没降下来,测试差不多
xxxxxxxxxx
/**
* <p>
* 优化后的 求next数组 方法
* </p>
*
* @param needle 1
* @return int[]
* @throws
* @author Eric
* @date 2019/5/23
**/
public int[] smartNext(String needle) {
int[] arr = new int[needle.length() + 1];
arr[0] = -1;
for (int i = 0; i < needle.length(); i++) {
if (i == 0) {
arr[i + 1] = 0;
} else {
arr[i + 1] = getK(needle, i);
}
}
return arr;
}
/**
* <p>
* 求next 函数 最大k值
* </p>
* @author Eric
* @date 2019/5/23
* @param needle 字符串
* @param i 字符串 偏移位置
* @return int
* @throws
**/
private int getK(String needle, int i) {
for(int k=i;k>0;k--){
for(int j=1;j<=k;j++){
if(needle.charAt(k-j)!=needle.charAt(i+1-j)){
break;
}
if(j==k){
return k;
}
}
}
return 0;
}
百度到next优化
x
/**
* <p>
* 百度到最优 next 求解
* </p>
* @author Eric
* @date 2019/5/23
* @param needle 字符串
* @return int[]
* @throws
**/
public int [] fastNext(String needle){
int len = needle.length();
int [] next=new int[len+1];
next[0]=-1;
if(needle.length()==0){
return next;
}
//初始化
next[1]=0;
for(int i=1,k=0;i<len;i++) {
//这个while是最关键的部分
while(k>0 && needle.charAt(k)!=needle.charAt(i)){
k=next[k];
}
//等价于 k=next[next[i-1]-1]
//等号右边的k起的只是下标的作用
if(needle.charAt(k)==needle.charAt(i)){
//相等就+1
k++;
}
//赋值
next[i+1]=k;
}
return next;
}
三种next 时间测试结果
- 这里就多解释,百度的到时候复杂度是O(N) 级别的
BM算法
算法说明
感受: 个人觉得BF算法比KMP算法好理解多了,KMP最难理解就是next函数
算法实现
xxxxxxxxxx
/**
* <p>
* BF 算法实现的 indexOf() 方法
* 坏字符串概率
* 移动量=匹配字符串出现坏树的时候 匹配字符串的下标-源字符串(坏字符串)在被匹配字符串再次出现的下表
* A A A A A A becsdsddadadsd A 坏字符串
* |
* b A b d d a
* 偏移量=5-1 4
* </p>
* @author Eric
* @date 2019/5/22
* @param hayStack 源字符串
* @param needle 匹配字符串
* @return int 匹配的初始位置
* @throws
**/
public int bfIndexOf(String hayStack, String needle) {
if (needle.length() == 0) {
return 0;
}
//初始化长度
int hLen=hayStack.length()-1;
//初始化长度
int nLen=needle.length()-1;
//i 源字符串 偏移量
int i=nLen;
// 匹配字符串偏移量
int index=nLen;
while(i<=hLen){
// 源字符串向后匹配 偏移量
int yd=i;
while(index>=0){
if(hayStack.charAt(yd)==needle.charAt(index)){
//匹配成功 则向后匹配
yd-- ;
index--;
if(index<0){
return i-nLen;
}
}else{
//匹配失败则是坏字符串,匹配坏字符串是否有匹配的
int match=-1;
for(int j=index-1;j>=0;j--){
if(hayStack.charAt(yd)==needle.charAt(j)){
match=j;
break;
}
}
i+=index-match;
index=nLen;
break;
}
}
}
return index<0?i-nLen:-1;
}