数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学用于短文本的字符串搜索算法的Java程序
在这个问题中，我们需要找到模式在字符串中的索引。实现高效的文本搜索对于用户轻松搜索大型文本数据库非常重要。例如，您正在Microsoft Word中撰写博客或在VSCode中编写代码，其中包含10万个以上的单词。如果搜索算法效率低下，在搜索任何单词或句子时，显示搜索结果可能需要花费时间。
我们将学习两种不同的方法来实现字符串搜索算法。一种是朴素方法，另一种是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 - 初始化长度变量和'matches'以存储匹配的总数。
步骤2 - 从第0个索引遍历字符串到第(len_str - len_search)个索引。
步骤3 - 使用另一个嵌套循环来遍历搜索模式。
步骤4 - 如果字符串中第(p + q)个索引处的字符和搜索值中第q个索引处的字符不匹配，则中断循环。
步骤5 - 如果q等于len_search，则增加匹配次数并打印p值，因为我们找到了模式。
步骤6 - 最后，如果matcares等于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)，因为我们不使用任何额外空间。
方法二
KMP算法是由Knuth-Morris-Pratt发明的，这是一种非常高效的字符串搜索方法。KMP算法帮助我们在搜索模式时避免不必要的回溯。在朴素方法中，我们在长度为M的每个子字符串中搜索，但在这里我们不需要在给定字符串中回溯。
我们将为搜索值准备一个最长真前缀数组，并利用它来提高搜索效率。
算法
步骤1 - 在findMatch()函数中，定义所需的变量和longest_pref_suff[]数组以存储最长真前缀。
步骤2 - 执行processSuffPref()函数以填充lps数组。
步骤2.1 - 在processSuffPref()函数中，将第一个元素初始化为0。此外，定义prev_len并将其初始化为0，并将p初始化为1。
步骤2.2 - 进行迭代，直到p小于search_len。如果搜索模式中第p个索引处的字符与prev_len索引处的字符相同，则增加prev_len和p的值。此外，将prev_len值插入数组的第p个索引处。
步骤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，这是搜索值的起始索引。此外，使用longest_pref_suff[q - 1]更新q值。
步骤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算法可用于搜索包含数百万个单词的大型文本中的模式。
92 次查看
