알고리즘의 길이는 3

Question

의 문자열의 가장 자주 발생하는 순서를 찾을 수 : 이 시퀀스는 제 3 배열에 두 번 발생하기 때문에

Ana John Maria 
Paul 
Sharon Ana John Maria Tiffany Ted 

출력은 Ana John Maria 될 것입니다 : 3 개 배열을 감안할 때.

나는 이것을 위해 올바른 해결책을 찾을 수 없습니다.

누구나 올바른 방향으로 나를 가리킬 수 있습니까? 어쩌면 이것은 잘 알려진 알고리즘 일 것입니다. 누구나 내게 링크를 줄 수 있습니까? 감사합니다.

Answer 1

각 노드가 단일 문자가 아닌 전체 이름 인 트리와 유사한 트리에 배열을 병합하십시오. 이렇게하면 하위 시퀀스를 쉽게 찾고 찾을 수 있습니다. 사실, 나는 당신이 볼 수있는이 작업을위한 표준 알고리즘이 있다는 것을 강하게 의심합니다.

업데이트 : 접미사 트리를 사용하여 알고리즘을 봐 : 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)); 
    } 
}