算法练习_暴力子字符串查找算法

Posted on | Comments: | Views:
暴力子字符串查找算法的学习笔记以及代码实现

概念

子字符串查找

给定长为 N 的文本，以及长为 M 的模式，在字符串中查找匹配该模式的子字符串，例如我们常用的 ctrl+f 查找。模式相对于文本是很短的。

暴力子字符串查找

子字符串查找有一个简单而广泛的暴力法，它在最坏的情况下运行时间与 MN 成正比。该方法是在文本中模式可能出现的任何地方进行匹配检查。当检查到符合模式的第一个字符时，依次检查后续字符，若后续某一字符不匹配，则将计数置零，从当前字符重新进行匹配。

图解

kK5Kne.png

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Brute {

    public int search(String pat, String txt) {
        int N = pat.length();
        int M = txt.length();

        for (int i = 0; i <= M - N; i++) {
            int j;
            for (j = 0; j < N; j++) {
                //如果不匹配则重新计数
                if (pat.charAt(j) != txt.charAt(i + j)) {
                    break;
                }
            }
            //全部匹配成功，返回索引
            if (j == N) {
                return i;
            }
        }
        return M;
    }
}

参考文档

《算法》