주어진 단어와 텍스트, 우리는 anagrams의 발생을 반환해야합니다 .. 나의 접근 방식이 맞습니까?

Question

기본적으로 문제의 해결책을 찾으려고 노력 중입니다. Given a word and a text, we need to return the occurrences of anagrams. 그러나, 거기에 게시 된 솔루션의 일부를 이해할 수 없었습니다. 그래서, 문제를 주어진 텍스트의 순열 (permutations) 찾기 문제로 변환하려고했습니다. 여기에 내 알고리즘 (의사 코드)이 있습니다. ID는 복잡성을 찾는 데 필요한 통찰력과 올바른 통찰력을 제공합니다.

int findAnagramOccurencesinText(String input,String find) 

//generate a list of all possible permutations of the letters in find and store in a list 
// eg/ if find ="dog" then list =["god","odg","dog","gdo","ogd","dgo"] 

int occurances=0; 
for String (perm:list) 
{ 
    index=-1; 
    while(index<input.length) 
     { 
      index=input.indexOf(perm,index); 
      if(index!=-1) 
      occurances++; 
      index+=1; 

     } 
} 
return occurances; 
} 

또한 복잡도 O (#inputlength)도 있습니까? 이 알고리즘의 복잡성을 찾는 방법에 대한 통찰력 (올바른 경우)은 인정 될 것입니다.

편집 : 나는 이것이 O (! n)이 솔루션을 이해합니다. 더 효율적으로 만들기 위해 수정할 수 있습니까? (링크 질문 상기 (n)에 접근 전체 접근을 폐기하고 O 이동 이외)은

Answer 1

는 n 요소 세트의 순열 O(n!)있다.

그래서 알고리즘을 검색 문자열을 가정하면 선형 시간이, 시간 복잡도 것이다 :

O((findLength)! inputLength) 

위 수식 slightly more complicated이고, 그렇지 않은 경우 find가 중복없이 가정한다.