算法發現長度爲3

Question

串的最頻繁出現的序列「鑑於多個名稱陣列，發現長度爲3（長度爲3的序列）的名字出現頻率最高的序列，如果存在」

例如： 鑑於3個數組：

Ana John Maria 
Paul 
Sharon Ana John Maria Tiffany Ted 

的輸出將是Ana John Maria因爲該序列中遇到兩次，在第一和第三陣列。

我似乎無法找到正確的解決方案。

任何人都可以指向正確的方向嗎？也許這是一個衆所周知的算法。任何人都可以給我一個鏈接？ 謝謝

Answer 1

將數組合併到類似於trie的樹中，其中每個節點不是單個字母，而是整個名稱。這應該允許您更容易地查找和計數子序列。事實上，我強烈懷疑這個任務有一個標準算法，您可以查看它。

更新：看看使用後綴樹算法：http://en.wikipedia.org/wiki/Suffix_tree

Answer 2

一個簡單的方法是採取3個序列，並把它們放在一個HashTable。一旦遇到3的序列，你就增加相應的發生計數器。最後只需返回最常見的事件/序列。通過掃描HashTable找到具有最大出現值的條目，可以找到這個結果。 Java中的示例：

public class Sequence { 
    public List<String> sequenceOfThree(List<List<String>> names){ 
      Map<List<String>, Integer> map = new HashMap<List<String>, Integer>(); 
      for(List<String> nameList:names){ 
       int startIdx = 0; 
       int endIdx = 3; 
       while(endIdx <= nameList.size()){ 
        List<String> subsequence = nameList.subList(startIdx, endIdx); 
        //add to map 
        Integer count = map.get(subsequence); 
        if(count == null){ 
         count = 0; 
        } 
        map.put(subsequence, count + 1); 
        startIdx++; 
        endIdx++; 
       } 
      } 
      Integer max = Integer.MIN_VALUE; 
      List<String> result = Collections.emptyList(); 
      for(Entry<List<String>, Integer> entries:map.entrySet()){ 
       if(entries.getValue() > max){ 
        max = entries.getValue(); 
        result = entries.getKey(); 
      } 
     } 
     return result; 
    } 
    /** 
    * @param args 
    */ 
    public static void main(String[] args) { 
     List<List<String>> names = new ArrayList<List<String>>(); 
     names.add(Arrays.asList(new String[]{"Ana", "John", "Maria"})); 
     names.add(Arrays.asList(new String[]{"Paul"})); 
     names.add(Arrays.asList(new String[] 
"Sharon", "Ana", "John", "Maria", "Tiffany" ,"Ted"})); 
     System.out.println(new Sequence().sequenceOfThree(names)); 
    } 
}