使用三种方法在文本中进行模式搜索

Question

我想要在给定文本中编写一个程序进行模式搜索，该文本读取文本，然后输入一个或多个模式，并为每个模式提供： 如果找到（打印出在文本中第一次出现的位置） 如果不是用于比较的方法中的数量：蛮力，博耶-摩尔启发式，和KMP。
但我不知道怎么写我的主类，以获取输出：

import java.util.HashMap; 
import java.util.Map; 


public class PatternSearch { 


/** Returns the lowest index at which substring pattern begins in text (or else -1).*/ 
public static int findBrute(char[] text, char[] pattern) { 
int n = text.length; 
int m = pattern.length; 
for (int i=0; i <= n - m; i++) { // try every starting index within text 
int k = 0; // k is index into pattern 
while (k < m && text[i+k] == pattern[k]) // kth character of pattern matches 
k++; 
if (k == m) // if we reach the end of the pattern, 
return i; // substring text[i..i+m-1] is a match 
} 
    return -1; // search failed 
} 

/** Returns the lowest index at which substring pattern begins in text (or else -1).*/ 
public static int findBoyerMoore(char[] text, char[] pattern) { 
    int n = text.length; 
int m = pattern.length; 
if (m == 0) return 0; // trivial search for empty string 
Map<Character,Integer> last = new HashMap<>(); // the 'last' map 
for (int i=0; i < n; i++) 
last.put(text[i], -1); // set -1 as default for all text characters 
for (int k=0; k < m; k++) 
last.put(pattern[k], k); // rightmost occurrence in pattern is last 
// start with the end of the pattern aligned at index m-1 of the text 
int i = m-1; // an index into the text 
int k = m-1; // an index into the pattern 
while (i < n) { 
     if (text[i] == pattern[k]) { // a matching character 
if (k == 0) return i; // entire pattern has been found 
i--; // otherwise, examine previous 
k--; // characters of text/pattern 
} else { 
     i += m - Math.min(k, 1 + last.get(text[i])); // case analysis for jump step 
k = m - 1; // restart at end of pattern 
} 
    } 
return -1; // pattern was never found 
} 


/** Returns the lowest index at which substring pattern begins in text (or else -1).*/ 
public static int findKMP(char[] text, char[] pattern) { 
int n = text.length; 
int m = pattern.length; 
if (m == 0) return 0; // trivial search for empty string 
int[] fail = computeFailKMP(pattern); // computed by private utility 
int j = 0; // index into text 
int k = 0; // index into pattern 
while (j < n) { 
if (text[j] == pattern[k]) { // pattern[0..k] matched thus far 
if (k == m - 1) return j - m + 1; // match is complete 
j++; // otherwise, try to extend match 
k++; 
} else if (k > 0) 
k = fail[k-1]; // reuse suffix of P[0..k-1] 
else 
j++; 
} 
return -1; // reached end without match 
} 


private static int[] computeFailKMP(char[] pattern) { 
int m = pattern.length; 
int[ ] fail = new int[m]; // by default, all overlaps are zero 
int j = 1; 
int k = 0; 
while (j < m) { // compute fail[j] during this pass, if nonzero 
if (pattern[j] == pattern[k]) { // k + 1 characters match thus far 
fail[j] = k + 1; 
j++; 
k++; 
    } else if (k > 0) // k follows a matching prefix 
    k = fail[k-1]; 
    else // no match found starting at j 
    j++; 
    } 
    return fail; 
    } 

public static void main(String[] args) { 



} 

}

Answer 1

看起来你是从C \ C++迁移到Java。

以下是如何通过main方法调用函数。因为你所有的方法都是静态的，所以我使用className.method（）方法调用了方法。

如果您的方法是非静态的，那么您将不得不创建该类的实例，然后使用您创建的实例调用该方法。

PatternSearch instance = new PatternSearch(); 
instance.findKMP(text.toCharArray(), pattern.toCharArray());