3

2つの文字列間の最大の共通部分文字列の問題を解決しようとしています。問題を次のように減らします。一般的な接尾辞木を作成しました。私の理解では、最大の共通サブ文字列は、両方の文字列に属するノードで構成される最も深いパスです。

私のテスト入力は次のとおりです。

String1 = xabc
String2 = abc

ここに画像の説明を入力してください

私が構築したツリーは正しいようですが、私の問題は次の方法です（最初にツリーのルートを渡します）。 

private void getCommonSubstring(SuffixNode node) {  
   if(node == null)  
    return;  
   if(node.from == ComesFrom.Both){  
    current.add(node);          
   }  
   else{  
    if(max == null || current.size() > max.size()){  
        max = current;              
    }  
    current = new ArrayList<SuffixNode>();   
   }  
   for(SuffixNode n:node.children){  
    getCommonSubstring(n);  
   }  
}

私が目指していたのは、両方の文字列に属するノードを持つ最も深いパスを見つけるために、ツリーをトラバースし（事前注文）、リストに両方の文字列に属するノードを追加することです（current）。両方の一部ではないノードに入ると、大きいmax場合はリストを更新します。current

しかし、コードは誤りです。そして、私はこれを実装する方法について混乱しています。なぜなら、私は昔から一般的な（非バイナリ）ツリーのコードを書いていなかったからです。

これを理解するのを手伝ってくれませんか。

更新：
@templatetypedefに従って変更されました。これも動作させることができませんでした。 

private void getCommonSubstring(SuffixNode node, List<SuffixNode> nodes) {  
   if(node == null)  
    return;  
   if(node.from == ComesFrom.Both){  
    nodes.add(node);              
   }  
   else{  
       if(max == null || current.size() > max.size()){  
       max = nodes;               
    }  
    nodes = new ArrayList<SuffixNode>();  
   }  
   for(SuffixNode n:node.children){  
    List<SuffixNode> tmp = new ArrayList<SuffixNode>(nodes);  
    getCommonSubstring(n, tmp);  
   }  
}  


public class SuffixNode {
    Character character;  
    Collection<SuffixNode> children;  
    ComesFrom from;  
    Character endMarker;  
}
4

4 に答える 4

2

ここで私が見ている問題の1つは、接尾辞ツリーのノードの深さが、そのパスに沿った文字列の長さと同じではないということです。接尾辞木の各エッジには文字の範囲が注釈として付けられているため、深さ5の一連のノードでエンコードされた文字列は、深さ2でエンコードされた文字列よりも長さが短くなる可能性があります。これまでにトレースしたパス内のノードの数ではなく、これまでに作成した文字列の有効な長さを追跡することによって、これを処理するようにアルゴリズムを調整する必要があります。

current私が今気付いた2番目の問題は、再帰のすべての異なるブランチ間で共有されている変数が1つしかないように見えることです。これはおそらく、再帰呼び出し全体で状態を台無しにしている可能性があります。たとえば、ノードにいて長さが3のパスがあり、2つの子があるとします。最初の子は最初の文字列のサフィックスでのみ終了し、2番目の子は次のサフィックスで終了します。両方の文字列。その場合、最初の文字列に対して再帰呼び出しを行うと、その行を実行することになります。

current = new ArrayList<SuffixNode>();

再帰呼び出しで。これによりすべての履歴がクリアされるため、この呼び出しから元のノードに戻って2番目の子ノードに降りると、から続行するのではなく、これまでに構築されたノードのリストがないかのように動作します。これまでに見つけた3つのノード。

これを修正するには、既存のを一掃するのではなくcurrent、関数にパラメーターを作成し、必要に応じて新しいパラメーターを作成することをお勧めします。これを説明するために、他のロジックの一部も変更する必要がある場合があります。ArrayListArrayList

これを考えると、次のような擬似コードで関数を作成することをお勧めします（接尾辞木の実装の詳細がわからないため）。

  • 現在のノードがnullの場合、0を返します。
  • 現在のノードが両方の文字列に由来しない場合は、0を返します。
  • さもないと：
    • maxLen=0に設定します。
    • 子ノードごとに：
      • そのノードをルートとする最長の共通サブストリングの長さを計算します。
      • その長さに、その子の端に沿った文字数を追加します。
      • これが古い値を超える場合は、maxLenを更新します。
    • maxLenを返します。

お役に立てれば！

于 2013-01-03T20:45:36.903 に答える
1

答えではありませんが、これは、O（n log n）ルックアップを使用した標準コレクションを使用して解決する方法です。

static String findLongestCommonSubstring(String s1, String s2) {
    if (s1.length() > s2.length()) return findLongestCommonSubstring(s2, s1);

    NavigableSet<String> substrings = new TreeSet<>();
    for (int i = 0; i < s1.length(); i++)
        substrings.add(s1.substring(i));
    String longest = "";
    for (int i = 0; i < s2.length(); i++) {
        String sub2 = s2.substring(i);
        String floor = match(substrings.floor(sub2), sub2);
        String ceiling = match(substrings.ceiling(sub2), sub2);
        if (floor.length() > longest.length())
            longest = floor;
        if (ceiling.length() > longest.length())
            longest = ceiling;
    }
    return longest;
}

private static String match(String s1, String s2) {
    if (s1 == null || s2 == null) return "";
    for (int i = 0; i < s1.length() && i < s2.length(); i++)
        if (s1.charAt(i) != s2.charAt(i))
            return s1.substring(0, i);
    return s1.substring(0, Math.min(s1.length(), s2.length()));
}

public static void main(String... args) {
    System.out.println(findLongestCommonSubstring("sdlkjfsdkljfkljsdlfkjaeakjf", "kjashdkasjdlkjasdlfkjaesdlk"));
}

プリント

sdlfkjae
于 2013-01-03T21:59:57.097 に答える
0

接尾辞木のルートに行く必要がありますか？そうでない場合、なぜあなたはできませんでした：

public String findCommonSubString(string str1, string str2) {
   string mainStr;
   string otherStr;
   string commonStr = "";
   string foundCommonStr = "";
   boolean strGrowing = false;

   If (str1.length() > str2.length()) {
      mainStr = str1;
      otherStr = str2;
   } else {
      mainStr = str2;
      otherStr = str1;
   }

   int strCount = 0;

   for(int x = 0; x < mainStr.length();x++) {
      strCount = 1;
      strGrowing = true;

      while(strGrowing) {
         if (otherStr.IndexOf(mainStr.substring(x, strCount) >= 0) {
            //Found a match now add a character to it.
            strCount++;

            foundCommonStr = mainStr.substring(x, strCount);

            if (foundCommonStr.length() > commonStr.length()) {
               commonStr = foundCommonStr;
            }
         } else {
            strGrowing = false;
         }
      }

   }

return commonStr;

}

私はこれを実行していません...しかし、実行します。基本的に、これは2つの文字列のうち最小のものから開始し、IndexOfとsubstringを使用して2つの文字列間の共通の文字列を見つけようとします。その後、再度チェックしますが、今回は小さい文字列からもう1文字をチェックに追加してチェックします。見つかった文字列（foundCommonStr）がcommonStrより大きい場合にのみ、文字列をcommonStr変数に格納します。一致するものが見つからない場合は、返される最大のcommonStrがすでに保存されています。

アイデアは正しいと思いますが、コンパイラでこれを実行していません。

于 2013-01-03T21:02:23.147 に答える
0 
public String findCommonSubString(string str1, string str2) {
   string mainStr;
   string otherStr;
   string commonStr = "";
   string foundCommonStr = "";
   boolean strGrowing = false;

   If (str1.length() > str2.length()) {
      mainStr = str1;
      otherStr = str2;
   } else {
      mainStr = str2;
      otherStr = str1;
   }

   int strCount = 0;

   for(int x = 0; x < mainStr.length();x++) {
      strCount = 1;
      strGrowing = true;

      while(strGrowing) {
         if (otherStr.IndexOf(mainStr.substring(x, strCount) >= 0) {
            //Found a match now add a character to it.
            strCount++;

            foundCommonStr = mainStr.substring(x, strCount);

            if (foundCommonStr.length() > commonStr.length()) {
               commonStr = foundCommonStr;
            }
         } else {
            strGrowing = false;
         }
      }

   }

return commonStr;

}
于 2014-03-20T11:43:01.663 に答える