在Java中，字符串匹配算法常常被用来从大段文本中搜索并找到指定的字符串。本实验报告将介绍如何使用Java实现三种常见的字符串匹配算法：朴素算法、KMP算法以及Boyer-Moore算法。

1、朴素算法

朴素算法是最简单的字符串匹配算法，它从文本的第一个字符开始遍历，并比较其与待匹配字符串的第一个字符是否相同，若相同则继续比较下一个字符，若不同则移动文本指针到下一个字符继续匹配。当匹配成功时，返回文本指针当前所在位置，否则返回-1。

以下是朴素算法的Java代码：

public static int naiveSearch(String text, String pattern) {
  int n = text.length();
  int m = pattern.length();
  for (int i = 0; i <= n - m; i++) {
    int j = 0;
    while (j < m && text.charAt(i + j) == pattern.charAt(j))
      j++;
    if (j == m)
      return i;
  }
  return -1;
}

2、KMP算法

KMP算法是一种更为高效的字符串匹配算法，它利用已知信息避免了在匹配过程中的重复匹配。它的核心思想在于，当一个字符与待匹配字符不匹配时，我们考虑从已知信息中找到与待匹配字符相同的位置继续匹配。这里的“已知信息”指的是主串中每个位置对应的最长公共前后缀长度。

以下是KMP算法的Java代码：

public static int kmpSearch(String text, String pattern) {
  int n = text.length();
  int m = pattern.length();
  int[] next = getNext(pattern);
  int i = 0, j = 0;
  while (i < n && j < m) {
    if (j == -1 || text.charAt(i) == pattern.charAt(j)) { //匹配成功或pattern的第一个字符就与text的当前字符不匹配
      i++;
      j++;
    } else {
      j = next[j];
    }
  }
  if (j == m)
    return i - m;
  else
    return -1;
}
private static int[] getNext(String pattern) {
  int m = pattern.length();
  int[] next = new int[m];
  next[0] = -1;
  int i = 0, j = -1;
  while (i < m - 1) {
    if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
      i++;
      j++;
      next[i] = j;
    } else {
      j = next[j];
    }
  }
  return next;
}

3、Boyer-Moore算法

Boyer-Moore算法是一种更为高级的字符串匹配算法，它基于两种主要的启发策略：坏字符规则和好后缀规则。其中坏字符规则利用失配位置的字符在pattern中最后出现的位置和在text中的位置计算移动量，而好后缀规则利用已经匹配的相同前缀和pattern后缀来计算移动量。

以下是Boyer-Moore算法的Java代码：

public static int boyerMooreSearch(String text, String pattern) {
  int n = text.length();
  int m = pattern.length();
  int[] badChar = new int[256];
  int[] goodSuffix = new int[m];
  buildBadChar(badChar, pattern);
  buildGoodSuffix(goodSuffix, pattern);
  int i = m - 1, j = m - 1;
  while (i < n && j >= 0) {
    if (text.charAt(i) == pattern.charAt(j))
      i--;
      j--;
     else {
      i += m - Math.min(j, 1 + badChar[text.charAt(i)]);
      j = m - 1;
    }
  }
  if (j == -1)
    return i + 1;
  else
    return -1;
}
private static void buildBadChar(int[] badChar, String pattern) {
  int m = pattern.length();
  for (int i = 0; i < 256; i++) {
    badChar[i] = -1; // 其中字符没有在pattern中出现过的置为-1
  }
  for (int i = 0; i < m; i++) {
    badChar[pattern.charAt(i)] = i; // 其中字符在pattern中最后出现的位置
  }
}
private static void buildGoodSuffix(int[] goodSuffix, String pattern) {
  int m = pattern.length();
  int[] suffix = new int[m]; // suffix[i]表示pattern的后缀中长度为i+1的最长相同前后缀的末尾位置
  suffix[suffix.length - 1] = suffix.length;
  for (int i = suffix.length - 2; i >= 0; i--) {
    int j = i;
    while (j >= 0 && pattern.charAt(j) == pattern.charAt(suffix.length - (i - j) - 1))
      j--;
    
    suffix[i] = i - j;
  }
  Arrays.fill(goodSuffix, m);
  int j = 0;
  for (int i = m - 1; i >= 0; i--) {
    if (suffix[i] == i + 1) {
      while (j < m - 1 - i) {
        if (goodSuffix[j] == m) {
          goodSuffix[j] = m - 1 - i;
        }
        j++;
      }
    }
  }
  for (int i = 0; i < m - 1; i++) {
    goodSuffix[m - 1 - suffix[i]] = m - 1 - i;
  }
}

相似文章

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政