Java 实现用于短文本大小的字符串搜索算法

在这个问题中，我们需要找到字符串中模式的索引。实现高效的文本搜索非常重要，以使用户能够轻松搜索大型文本数据库。例如，您正在Microsoft Word中撰写博客或在VSCode中编写代码，其中包含1 lakh以上的单词。如果搜索算法效率低下，搜索任何单词或句子时可能需要时间才能显示搜索结果。

我们将学习两种不同的方法来实现字符串搜索算法。一种是朴素方法，另一种是KMP算法。

问题描述 - 给定一个字符串str和不同长度的搜索值。我们需要找到给定字符串中搜索值的索引。

示例

输入

str = "welcome to Tutorialspoint for well organized tutorials and libraries!", 
searchValue = "wel";

输出

0, 30

解释: - 它打印出str中搜索值的起始位置。

输入:

str = "Apple is good! Apple is Awesome! Apples are amazing!", searchValue = 
"Apple is"

输出

0, 15

解释 - 在给定的字符串中，“Apple is”出现了两次。

输入

str = 'Hello! Are you fine?”, searchValue = “How”

输出

-1

解释 - 由于在字符串中找不到搜索值，因此打印-1。

方法1

这是一种天真的方法，我们将检查长度等于搜索值长度的每个子字符串以找到匹配的结果。

算法

步骤1 - 初始化长度变量和’matches’以存储匹配的总数。

步骤2 - 从0索引到(len_str – len_search)索引遍历字符串。

步骤3 - 使用另一个嵌套循环来遍历搜索模式。

步骤4 - 如果字符串中(p + q)索引处的字符和搜索值中第q个索引处的字符不匹配，则停止循环。

步骤5 - 如果q等于len_search，则增加匹配，并打印p值，因为我们找到了该模式。

步骤6 - 最后，如果match值等于0，则打印-1，因为我们在字符串中找不到任何搜索值。

代码

import java.io.*;
public class Main {
   // Function to find string matches
   public static void FindMatch(String str, String searchValue) {
      int len_str = str.length();
      int len_search = searchValue.length();
      int matches = 0;
      // Traverse the string
      for (int p = 0; p <= (len_str - len_search); p++) {
         int q;
         for (q = 0; q < len_search; q++) {
            if (str.charAt(p + q) != searchValue.charAt(q))
               break;
         }
         if (q == len_search) {
            matches++;
            System.out.println("Pattern position is : " + p);
         }
      }
      if (matches == 0)
         System.out.println("No Pattern Found in the given string!");
      else
         System.out.println("Total search patterns found in the string are = " + matches);
   }
   public static void main(String[] args) {
      String str = "welcome to Tutorialspoint for well organized tutorials and libraries!";
      String searchValue = "wel";
      FindMatch(str, searchValue);
   }
}

输出

Pattern position is : 0
Pattern position is : 30
Total search patterns found in the string are = 2

时间复杂度 - O(N*M)，其中N是字符串长度，M是搜索值长度。

空间复杂度 - O(1)，因为我们没有使用额外的空间。

方法2

KMP算法是由Knuth-Morris-Pratt发明的，它是一种非常高效的字符串搜索方法。KMP算法帮助我们避免在搜索模式时发生不必要的回溯。在朴素方法中，我们在每个长度为M的子字符串中进行搜索，但在这里我们不需要在给定的字符串中回溯。

我们将准备一个最长前缀数组，用于帮助我们进行高效的搜索。

算法

步骤1 - 在findMatch()函数中，定义所需变量和longest_pref_suff[]数组以存储最长前缀。

步骤2 - 执行processSuffPref()函数以填充最长前缀数组。

步骤2.1 - 在processSuffPref()函数中，将第一个元素初始化为0。还需定义prev_len并初始化为0，p初始化为1。

步骤2.2 - 迭代直到p小于search_len。如果搜索模式中第p个索引处的字符与prev_len索引处的字符相同，则增加prev_len和p的值。同时，在数组中插入prev_len的值。

步骤2.3 - 如果字符不匹配且prev_len不等于零，则通过longest_pref_suf[prev_len-1]更新其值。否则，更新数组中第p个索引处的值并增加’p’的值。

步骤3 - 在下一步中，将p和q初始化为0。此后，开始对字符串和模式进行迭代。

步骤4 - 如果search.charAt(q) str.charAt(p)为真，将p和q都增加1以前进。

步骤5 - 如果q search_len为真，则打印p – q，即搜索值的起始索引。同时，将q的值更新为longest_pref_suff[q-1]。

步骤6 - 如果q不等于search_len且str中索引p和搜索字符串中索引q的字符不相同，请按照以下步骤进行。

步骤7 - 如果q不为零，则更新q的值；否则，将p增加1。

代码

public class Main {
   public static void processSuffPref(String search, 
   int search_len, int longest_pref_suf[]) {
      // variable to store the length of the previous prefix
      int prev_len = 0;
      int p = 1;
      longest_pref_suf[0] = 0; // This is always 0
      while (p < search_len) {
         if (search.charAt(p) == search.charAt(prev_len)) {
            prev_len++;
            longest_pref_suf[p] = prev_len;
            p++;
         } else // If it doesn't match
         {
            if (prev_len != 0) {
               prev_len = longest_pref_suf[prev_len - 1];
            } else {
               longest_pref_suf[p] = prev_len;
               p++;
            }
         }
      }
   }

   public static void FindMatch(String str, String search) {
      // Initialize lengths
      int str_len = str.length();
      int search_len = search.length();
      // array to store longest prefix and suffix values
      int longest_pref_suff[] = new int[search_len];
      // calculate the longest prefix and suffix values
      processSuffPref(search, search_len, longest_pref_suff);
      int p = 0; // string index
      int q = 0; // search index
      while (p < str_len) {
// If characters at q index in str and p index in p match, increment both pointers
         if (search.charAt(q) == str.charAt(p)) {
            q++; p++;
         }
         if (q == search_len) {
            System.out.println("Index of search value is - " + (p - q));
            q = longest_pref_suff[q - 1];
         }
         // If a pattern is not found after q matches
         else if (p < str_len && search.charAt(q) != str.charAt(p)) {
            if (q != 0)
               q = longest_pref_suff[q - 1];
            else
               p = p + 1;
         }
      }
   }
   public static void main(String args[]) {
      String str = "welcome to Tutorialspoint for well organized tutorials and libraries!";
      String searchValue = "wel";
      FindMatch(str, searchValue);
   }
}

输出

Index of search value is - 0
Index of search value is - 30

时间复杂度 - O(N + M)，因为在遍历字符串和模式时，我们不进行回溯。

空间复杂度 - O(M)，因为我们存储了搜索模式的最长前缀。

程序员可以观察到第一种和第二种方法的时间复杂度的差异。第一种方法比第二种方法花费的时间要多M倍。KMP算法可以用于在包含数百万字的大文本中搜索模式。