设文本长度为N,要匹配的模式的长度为M,暴力查找算法在最坏的情况下运行时间与MN成正比,但在处理许多应用程序中的字符串时,它的实际运行时间一般与M+N成正比。
实现方法1:
使用一个值指针i跟踪文本,一个指针j跟踪要匹配的模式,对每一个i,代码首先将j重置为0并不断增大,直到找到了一个不匹配的字符或者是匹配成功(j==M)。
public static int search(String pat, String txt) {
int M = pat.length();
int N = txt.length();
for(int i = 0;i<= N;i++) {
int j;
for(j=0;j<M;j++)
if(txt.charAt(i+j)!=pat.charAt(j))
break;
if(j==M) return i;
}
return N;
}
实现方法2(显式回退):
同样使用一个值指针i跟踪文本,一个指针j跟踪要匹配的模式,在i和j指向的字符匹配时,i和j同时后移一位。如果i和j字符不匹配,那么需要回退这两个指针,j指向模式的开头,i指向这次匹配开头的下一个字符。
public static int Search(String pat,String txt) {
int j, M = pat.length();
int i, N = txt.length();
for(i=0,j=0;i<N&&j<M;i++) {
if(txt.charAt(i)==pat.charAt(j)) j++;
else {i-=j;j=0;}
}
if(j==M) return i-M;
else return N;
}