0

文字列内の複数のパターンに一致する方法について多くの解決策を見つけましたが、単一の文字列を多くの単語に一致させる方法は見つかりませんでした。

これまでのところ、単語ごとに KMP アルゴリズムを使用するのが最善の方法ですが、これはあまり効率的ではありません (複雑さ = 単語の長さの合計)。そのため、より良いアルゴリズムを探しています。

4

1 に答える 1

2

あなたは根本的に問題を誤解しています。問題を簡単に分解して、単語内の文字列のすべての出現箇所を見つけることができます。これは、個々の文字列を1つの大きな文字列（または単語）に結合することによって行われます。次に、この大きな文字列を1回繰り返して、KMPや正規表現などの効率的なアルゴリズムを使用できます（ただし、正規表現の使用は必ずしも推奨されません）。私が何を意味するかを示す例： 

List<String> stringList = new ArrayList<String>();

    String first = "abc";  
    String second = "def";  
    String third = "xyz";  
    stringList.add(first);  
    stringList.add(second);  
    stringList.add(third);  

for(String string : stringList)  
{  
    kmp(string);  
}

次と同等です。 

List<String> stringList = new ArrayList<String>();  
stringList.add("abcdefxyz");  
for(String string : stringList)  
{  
   kmp(string);   
}

Kevinがコメントで指摘したように、ここで区切り文字を使用すると、誤った結果が生成されるのを防ぐことができます。

于 2012-07-19T11:34:13.063 に答える