java - 2 つの文字列から類似した部分文字列を見つける方法

Question

このJavaコードを使用して、同様の文字列を見つけています。

if( str1.indexof(str2) >= 0 || str2.indexof(str1) >= 0 ) .......

しかしstr1 = "pizzabase"、str2 = "namedpizzaowl"それは機能しません。

「pizza」などの一般的な部分文字列を見つけるにはどうすればよいですか?

Answer 1

の各文字を繰り返し、str1に存在するかどうかを確認しstr2ます。存在しない場合は、次の文字に移動します。存在する場合は、str1チェックインする部分文字列の長さstr2を2文字に増やし、一致するものが見つからなくなるか、を繰り返すまで繰り返しますstr1。

これにより、すべてのサブストリングが共有されますが、バブルソートのように、問題を解決する方法の非常に基本的な例であるため、ほとんど最適ではありません。

この疑似っぽい例のようなもの：

pos = 0
len = 1
matches = [];

while (pos < str1.length()) {

    while (str2.indexOf(str1.substring(pos, len))) {
       len++;
    }

    matches.push(str1.substring(pos, len - 1));
    pos++;
    len = 1;
}

Answer 2

アルゴリズムが、共通の部分文字列を含む 2 つの文字列が類似していると判断した場合、このアルゴリズムは常に true を返します。空の文字列""は自明ですが、すべての文字列の部分文字列です。また、文字列間の類似度を判断し、ブール値ではなく数値を返す方が理にかなっています。

これは、文字列 (またはより一般的にはシーケンス) の類似性を判断するための優れたアルゴリズムです: http://en.wikipedia.org/wiki/Levenshtein_distance。