快速文本搜索

Question

我编写这段代码是为了在较大的文本中搜索一个小文本。到目前为止，进展非常缓慢。我该如何优化它？请帮我优化这段代码。

public class St {

/**
 * @param args the command line arguments
 */
public static void main(String[] args) throws IOException {
    // TODO code application logic here
    BufferedReader b1=new BufferedReader(new InputStreamReader(System.in));
    String s=b1.readLine();
    String t=b1.readLine();
    String news = null;
    //double u=t.hashCode();
    //double q=s.hashCode();
    //double x;
    //.out.print(u+"\n"+q);
    int x=t.length();
    int y=s.length();
    for(int i=0;i<y-x-1;i++){



            //news=s.substring(i, i+t.length());
             //x=news.hashCode();


            //System.out.println(news);
        if(t.equals(s.substring(i, i+x))){
           System.out.println(i);
        }
    }

}


}

Answer 1

虽然有更聪明的算法，但没有它们，您可以实现一些重要的改进。只需使用Java中的内容：

for (int i=hay.indexOf(needle); i!=-1; i=hay.indexOf(needle, i+1) {
    System.out.println(i);
}

您的算法非常慢，因为您需要n多次复制m字符来比较它们。这一个完全避免了抄袭。虽然实际字符串的复杂性仍然是O(m*n)，但它的性能要好得多，因为通常只需要比较几个字符。

Answer 2

您可以选择一种著名的算法，以及它们的实现，以便进行这种性质的搜索。

您的选项包括克努斯·莫里斯·普拉特、博耶·摩尔和拉宾·卡普算法。它们中的每一个都有自己的复杂性保证，根据您的输入数据，其中一个可能比另一个更好。

从易于实现的角度来看，Rabin具有一个体面的滚动散列函数，应该会给您提供可接受的性能。有一个可靠的实现提供了这里。

另一个非常好的选择可能值得探讨的是正则表达式。正则表达式引擎可能有一个快速实现的算法来执行这种性质的子字符串匹配。