您好,登錄后才能下訂單哦!
Knuth-Morris-Pratt(KMP)算法是一種高效的字符串匹配算法,它的時間復(fù)雜度為O(n+m),其中n和m分別是文本串和模式串的長度
public class KMPAlgorithm {
public static void main(String[] args) {
String text = "ABABC";
String pattern = "AB";
int[] lps = computeLPSArray(pattern);
int index = kmpSearch(text, pattern, lps);
if (index != -1) {
System.out.println("Pattern found at index: " + index);
} else {
System.out.println("Pattern not found");
}
}
// 計算最長前綴后綴數(shù)組(LPS數(shù)組)
public static int[] computeLPSArray(String pattern) {
int[] lps = new int[pattern.length()];
int len = 0;
int i = 1;
while (i < pattern.length()) {
if (pattern.charAt(i) == pattern.charAt(len)) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
// KMP搜索算法
public static int kmpSearch(String text, String pattern, int[] lps) {
int n = text.length();
int m = pattern.length();
int i = 0; // 指向text的指針
int j = 0; // 指向pattern的指針
while (i < n) {
if (pattern.charAt(j) == text.charAt(i)) {
i++;
j++;
}
if (j == m) {
System.out.println("Pattern found at index: " + (i - j));
j = lps[j - 1];
} else if (i < n && pattern.charAt(j) != text.charAt(i)) {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
return -1; // 如果未找到模式串,返回-1
}
}
這個程序首先計算模式串的最長前綴后綴數(shù)組(LPS數(shù)組),然后使用KMP搜索算法在文本串中查找模式串。如果找到模式串,程序?qū)⑤敵銎湓谖谋敬械钠鹗妓饕?/p>
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。