暴力子字符串查找算法另一种实现_显示回退

算法思路:
指针 i 跟踪txt,这里的i指向的是文本中已经匹配过的字符序列的末端( i + j )
指针 j 跟踪pattern
如果 i 和 j 指向的字符不匹配了,那么需要回退这两个指针的值,
将j重新指向模式的开头0,
将 i 指向本次匹配的开始位置的下一个字符,
因为 i = i + j,所以回退的时候 , i - = j,
因为是从0开始,所以 i 为本次匹配开始位置的下一个字符.

如果 i 和 j指向的字符匹配,那么 j++;
不匹配 则回退 i - = j ; j = 0;
如果j == M就意味着匹配成功,返回第一个匹配字符串的角标,因为i为匹配过的序列的末端,那么第一个匹配字符串的角标则为 i - M, M为pattern的长度
不匹配返回 -1

public class searchForOther {

    public static void main(String[] args) {
        int index = search("ABACADABRAC", "ABRA");
        System.out.println(index);
    }

    private static int search(String txt, String pattern) {
        int N = txt.length();
        int M = pattern.length();
        int i, j = 0;
        for (i = 0; i < N && j < M; i++) {
            if (txt.charAt(i) == pattern.charAt(j))
                j++;
            else {
                i -= j;
                j = 0;
            }
        }
        if(j==M)
            return i-M;
        return -1;
    }

}