Java实现bf算法和kmp算法

以下是Java实现BF算法和KMP算法的例子：

BF算法实现：

public class BFAlgorithm {
 public static int bfSearch(String text, String pattern) {
 int n = text.length();
 int m = pattern.length();

 for (int i = 0; i <= n - m; i++) {
     int j;
     for (j = 0; j < m; j++) {
         if (text.charAt(i + j) != pattern.charAt(j)) {
             break;
         }
     }
     if (j == m) {
         return i;
     }
 }
 return -1;
 }
 public static void main(String[] args) {
 String text = "ABABABABC";
 String pattern = "ABC";
 int index = bfSearch(text, pattern);
 if (index != -1) {
     System.out.println("Pattern found at index " + index);
 } else {
     System.out.println("Pattern not found");
 }
 }


}

2. KMP算法实现：

public class KMPAlgorithm {
public static int kmpSearch(String text, String pattern) {
int n = text.length();
int m = pattern.length();

int[] lps = computeLPSArray(pattern);

int i = 0;
int j = 0;
while (i < n) {
if (text.charAt(i) == pattern.charAt(j)) {
i++;
j++;
if (j == m) {
return i - j;
}
} else {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
return -1;
}

private static int[] computeLPSArray(String pattern) {
int m = pattern.length();
int[] lps = new int[m];
int len = 0;
int i = 1;

while (i < m) {
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;
}

public static void main(String[] args) {
String text = "ABABABABC";
String pattern = "ABC";
int index = kmpSearch(text, pattern);
if (index != -1) {
System.out.println("Pattern found at index " + index);
} else {
System.out.println("Pattern not found");
}
}
}
登录后复制