子字符串查找

文章目录
  1. 1. 暴力子字符串查找算法
    1. 1.1. KMP算法

算法4 官网地址

暴力子字符串查找算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int search(String pat,String txt)
{
int M = pat.length();
int N = txt.length();
for(int i=0;i<=N-M;j++)
{
int j = 0;
for(int j=0; j< M ;j++)
{
if(txt.charAt(i+j) != pat.charAt(j))
break;
}
if(j==M) return i;
}
return N;
}

在最坏情况下,暴力子字符串查找算法在长度为N的文本中查找长度为M的模式需要NM次比较。

KMP算法

主要思想:提前判断如何重新开始查找。