子字符串查找----暴力查找法
SuperHeroes
发布于 2018-05-30 09:59:31
发布于 2018-05-30 09:59:31
代码可运行
运行总次数：0
代码可运行
设文本长度为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;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2018.01.26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
推荐阅读
相关推荐
子字符串查找----KMP算法
更多 >
腾讯云开发者
