java - tree教學 - 後綴樹




在一般樹遍歷中發現最深的路徑,試圖找到最大的公共子串 (3)

你有沒有去後綴樹的路線? 如果沒有,為什麼你不能:

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;

}

我沒有跑這個...但我會的。 基本上,這將從兩個字符串中最小的字符串開始,並嘗試使用IndexOf和子字符串在兩個字符串之間找到一個公共字符串。 那麼如果是這樣,它會再次檢查,但這次檢查通過從更小的字符串添加一個字符到檢查。 如果找到的字符串(foundCommonStr)大於commonStr,它將只存儲在commonStr變量中的字符串。 如果它沒有找到匹配,那麼它已經存儲了最大的commonStr被返回。

我相信這個想法是合理的,但我沒有在編譯器中運行。

我正在嘗試解決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;  
}  

我在這裡看到的一個問題是,後綴樹中節點的深度與沿該路徑的字符串的長度不同。 後綴樹中的每條邊都用一系列字符註釋,所以由深度為5的一系列節點編碼的字符串可能比在深度為2時編碼的字符串短。 您可能需要調整您的算法來處理這個問題,方法是跟踪您迄今為止建立的字符串的有效長度,而不是跟踪到此點的路徑中的節點數。

我剛剛注意到的第二個問題是,您似乎只有一個current變量在遞歸的所有不同分支之間共享。 這可能是在遞歸調用中搞亂了你的狀態。 例如,假設你在一個節點上,並且有一個長度為3的路徑,並且有兩個子節點 - 第一個子節點只以第一個字符串的後綴結尾,第二個子節點以兩個字符串。 在這種情況下,如果您對第一個字符串進行遞歸調用,那麼您將最終執行該行

current = new ArrayList<SuffixNode>();  

在遞歸調用中。 這將清除所有的歷史記錄,所以當你從這個調用返回到原始節點並下降到第二個子節點時,你將會像現在沒有建立節點的列表一樣工作,而不是繼續從到目前為止您發現的三個節點。

為了解決這個問題,我建議為current的函數創建一個參數,然後在需要時創建一個新的ArrayList ,而不是清除現有的ArrayList 。 其他一些邏輯可能也必須改變以解釋這一點。

鑑於此,我建議像這樣用偽代碼編寫函數(因為我不知道後綴樹實現的細節):

  • 如果當前節點為空,則返回0。
  • 如果當前節點不是來自兩個字符串,則返回0。
  • 除此以外:
    • 設置maxLen = 0。
    • 對於每個子節點:
      • 計算以該節點為根的最長公共子串的長度。
      • 將該邊緣的字符數添加到該子節點。
      • 如果超過了舊值,則更新maxLen。
    • 返回maxLen。

希望這可以幫助!


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;

}