hellogaon

접미사 배열(Suffix Array)은 어떤 문자열의 모든 접미사를 사전순으로 정렬해 둔 배열입니다.이를 구하기 위해 문자열의 접미사들을 모아놓은 뒤 정렬을 하게 되면길이가 N인 문자열의 접미사의 개수는 N개 이므로 O(NlgN)번 비교연산을 진행하지만string은 한 번 비교연산을 할 때마다 틀릴 때까지 앞글자부터 하나하나 비교를 하기에 시간복잡도가 O(N^2 lgN)입니다.이 때 좀 더 빠르게 접미사 배열을 만들기 위하여 맨버-마이어스 알고리즘을 사용합니다.접미사들의 특성을 이용하여 매번 접미사를 첫 한글자, 두글자, 네글자, 여덟글자... 기준으로 정렬하며매번 이전 정렬에서 얻은 정보를 이용하여 두 문자열을 빠르게 대소 비교합니다.이러한 과정으로 진행하면 비교연산을 O(lgN)번으로 줄일 수 있으며..

아호-코라식(Aho-Corasick)은 다중 문자열 검색을 하게 해주는 알고리즘입니다.이전의 KMP 알고리즘에서 길이가 N인 문자열에서 길이가 M인 문자열 하나를 검색하는 데의 시간복잡도가 O(N + M) 였기에길이가 N인 문자열에서 길이가 각각 m1, m2, m3...인 문자열 여러 개를 검색할 경우이에 대한 시간 복잡도는 O(N + m1 + N + m2 + N + m3...)입니다.이 때 아호-코라식 알고리즘은 이를 P는 검색할 문자열의 출현 횟수 일 때O(N + m1 + m2 + m3... + P)와 같은 시간 복잡도로 N을 1번만 본 뒤 계산을 합니다.그렇기에 이는 긴 문자열에서 많은 문자열을 찾아야 할 경우 사용하면 효율적인 알고리즘입니다.아호-코라식 알고리즘은 아래와 같은 정보들을 추가적으로 ..

트라이(Trie)는 문자열의 집합을 표현하는 트리 자료구조입니다.STL로 문자열의 집합을 표현하려면 set을 사용합니다.set에서 검색할 때는 O(lgN)번 비교연산을 진행하지만string은 한 번 비교연산을 할 때마다 틀릴 때까지 앞글자부터 하나하나 비교를 하기에문자열의 길이가 M일 경우 시간복잡도가 O(MlgN)이 됩니다.이를 O(M)만에 탐색하기 위해 트라이 자료구조를 사용합니다.트리 형태를 이용하여 다음에 나올 글자에 해당하는 노드가 있을 경우그 노드로 바로 이동하여 다음 글자를 탐색합니다.그 노드로 바로 이동하기 위해 다음 글자를 가능한 글자들을 가리키는 여러 개의 포인터 배열이 필요한데이는 많은 메모리를 낭비하게 되는 단점이 있습니다.이렇기 때문에 트라이를 사용해야하는 문제에서는 입력 데이터의..

KMP(Knuth Morris Pratt)는 문자열 검색 알고리즘입니다.길이가 H인 문자열에서 길이가 N인 문자열을 검색하고 싶을 경우완전탐색으로 보게 된다면 시간복잡도가 O(HN)이 되지만KMP는 O(H + N)만에 문자열을 검색하게 해주는 알고리즘입니다.기본적인 원리는 문자열을 검색하다가 일치하지 않는 부분이 나왔을 경우H의 다음 글자와 N의 처음부터 비교하는 것이 아닌지금까지 일치했던 부분의 접미사도 되고 접두사도 되는 문자열의 최대 길이만큼은 또 다시 일치하므로그 길이 이후부터 비교해 나가는 방식입니다.이 때, 접미사도 되고 접두사도 되는 문자열의 최대 길이를 저장해놓은 테이블을부분 일치 테이블이라고 부르는데 이를 구하는 방법 또한N에서 자신을 제외하고 N을 찾는 방법으로 구할 수 있기에비슷한 두..