목록기록/알고리즘 (1)

코드코코

210913 KMP

/* 트라이 : 다중검색, 접두사 패턴일치 확인에 뛰어나다. 보이어 무어 : 끝 부분이 일치하지 않으면 처음부분을 비교해보지 않는다는 가정아래 패턴의 처음이 아닌 마지막 문장를 비교한다. 인덱스를 뛰어 넘을 수 있기 때문에 텍스트 양이 많은 경우 효율적이다. KMP: 문자열 내에 패턴의 등장 횟수를 검색. 텍스트양이 적은 경우 효율적. 텍스트 편집기 어플리케이션과 웹 브라우저 찾기 기능에 사용된다. KMP는 텍스트 T에서 단어 W의 출현 횟수를 검색. 이 때 잘못된 일치가 발생이 되면 다음 일치가 어디에서 시작될수 있는지에 대한 충분한 정보를 얻을 수 있다라는 점을 활용. 이것은 이미 일치한 문자들을 다시 검사하는 것을 막아준다. 접두사 배열을 만들 때 접주사 배열이 동일한 접두사를 얻기위해 인덱스를 얼..
기록/알고리즘 2021. 9. 13. 23:13
이전 Prev 1 Next 다음