子字符串查找算法

2022/8/14 1:23:18

本文主要是介绍子字符串查找算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

子字符串查找算法:

  • 暴力子字符串查找算法
  • KMP 算法
  • RM 算法

术语:

  • 文本:完整的字符串
  • 模式字符串:需要在文本中查找的子串

暴力子字符串查找算法

性能:

  • 在极端情况下(存在很多重复的字符),时间复杂度是 O(MN)
  • 一般情况下(不需要完整地比对模式串),时间复杂度是 O(M + N)

思路:枚举出文本中的所有和模式串长度相等的子串进行对比

算法实现1:

public class BruteForce1 {
    public static int search(String txt, String pattern) {
       int n = txt.length();
       int m = pattern.length();
        for (int i = 0; i <= n - m; i++) {
            int j;
            for (j = 0; j < m; j++) {
                if (pattern.charAt(j) != txt.charAt(j + i)) {
                    break;
                }
            }
            if (j == m) {
                return i;
            }
        }
        return -1;
    }
}

测试:

class BruteForce1Test {
    @Test
    void search() {
        Assertions.assertEquals(0, BruteForce1.search("Hello World", "Hello"));
        Assertions.assertEquals(6, BruteForce1.search("Hello World", "World"));
        Assertions.assertEquals(-1, BruteForce1.search("Hello World", "Hi"));
    }
}

思路:枚举文本的每个和模式串长度相同的子串,对比失败时回退指针 i, j

算法实现2:

public class BruteForce2 {
    public static int search(String txt, String pattern) {
        int n = txt.length();
        int m = pattern.length();
        int i, j;
        for (i = 0, j = 0; i < n && j < m; i++) {
            if (pattern.charAt(j) == txt.charAt(i)) {
                j++;
            } else {
                i -= j;
                j = 0;
            }
        }
        if (j == m) {
            return i - m;
        }
        return -1;
    }
}

测试:

class BruteForce2Test {
    @Test
    void search() {
        Assertions.assertEquals(0, BruteForce2.search("Hello World", "Hello"));
        Assertions.assertEquals(6, BruteForce2.search("Hello World", "World"));
        Assertions.assertEquals(-1, BruteForce2.search("Hello World", "Hi"));
    }
}

KMP 算法

本节重点:

  • DFA 如何使用
  • DFA 如何构造

全称:Knuth-Morris-Pratt 子字符串查找算法(三位发明者的名字)

基本思想:利用已经比较过的字符信息,实现在匹配失败时,总是将 j 设置为某个值使 i 不回退

可能性:当匹配失败时,可以将模式串向右移动来避免指针 i 回退

文本串:AABAABAAAB
模式串:AABAAA 
    ->    AABAAA

实现:对模式串进行预处理,构造 DFA(确定有限状态自动机),在遍历文本串的字符时,可以从 DFA 得到下一个 j 的值,即状态

DFA: dfa[txt.chatAt(i)][j] 的值是和文本串的下一个字符 txt.chatAt(i+1) 比较的 j 值

算法实现:

public class KMP {
    private static final int R = 256; // 字符集大小
    private String pattern;
    private int m;
    private int[][] dfa;

    /**
     * 根据模式串构造确定有限状态自动机 DFA
     * */
    public KMP(String pattern) {
        this.pattern = pattern;
        this.m = pattern.length();
        dfa = new int[R][m];
        // 初始化第一列
        dfa[pattern.charAt(0)][0] = 1;
        // 初始化其他的列,从第二列开始
        // 当 txt[i..i+j] 匹配失败时,从 txt[i+1] 开始匹配,
        // 这里可以想象成DFA正在处理第 2 个字符的匹配情况
        // X 记录重启状态
        for (int j = 1, X = 0; j < m; j++) {
            for (int c = 0; c < R; c++) {
                dfa[c][j] = dfa[X][j]; // 匹配失败,将 dfa[][X] 复制到 dfa[][j]
            }
            dfa[pattern.charAt(j)][j] = j + 1; // 匹配成功,将 dfa[pattern.charAt(j)][j] 设置成 j + 1
            X = dfa[pattern.charAt(j)][X]; // 更新 X,即从 txt[i+1] 开始匹配或者说在构建自动的同时也在使用自动机
        }
    }

    /**
     * 在文本串中查找子串
     * 将文本串的字符逐个放到 DFA 中,直到 DFA 达到终止状态或文本串结束
     * */
    public int search(String txt) {
        int n = txt.length();
        int i, j;
        for (i = 0, j = 0; i < n && j < m; i++) {
            j = dfa[txt.charAt(i)][j];
        }
        if (j == m) {
            return i - m;
        }
        return -1;
    }
}

测试:

class KMPTest {
    @Test
    void search() {
        KMP kmp = new KMP("Hello");
        Assertions.assertEquals(0, kmp.search("Hello World"));
        Assertions.assertEquals(4, kmp.search("Say Hello"));
        Assertions.assertEquals(-1, kmp.search("hello world"));
    }
}

应用场景:

  • 文本串和模式串的重复性很高
  • 文本串是长度不确定的输入流


这篇关于子字符串查找算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程