資料結構
網路
關係資料庫管理系統 (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 次檢視
