Suffix Array 썸네일형 리스트형 BOJ)13576 Prefix와 Suffix 문제: icpc.me/13576 prefix와 suffix가 같은 모든 부분문자열은 pi배열을 이용하여 전부 구해줄 수 있다. length -> pi[length] -> pi[[pi[length]]] ... 이런식으로 하지만 이때 부분 문자열의 등장횟수도 구해줘야 한다. suffix의 부분 문자열 등장횟수는 LCP를 이용하여 O(N)에 처리해줄 수 있다. 현재 확인중인 i번째 suffix의 등장횟수는 LCP[i+1]~ LCP[max] 중에서 연속으로 부분 문자열 i의 길이보다 큰 LCP의 개수로 처리해줄 수 있다. 아래 코드에서 dp배열에 suffix의 등장횟수가 담긴다. 12345678910111213141516171819202122232425262728293031323334353637383940414.. 더보기 BOJ)11479 서로 다른 부분 문자열의 개수2 문제:icpc.me/11479 서로 다른 부분 문자열의 개수를 세는 문제이다. Suffix Array를 이용하여 LCP Array를 구해준 뒤 0~n 에 대하여 n-SA[i]-LCP[i](해당 Suffix의 길이-LCP) 의 합을 구해주면 된다. 해당 Suffix의 부분 문자열의 경우의 수는 해당 Suffix의 길이지만 이때 LCP만큼 중복되기 때문이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include #include typedef long long ll;#define MAX_N 1000010using namespace std;char.. 더보기 BOJ)9249 최장 공통 부분 문자열 문제: icpc.me/9249 http://jason9319.tistory.com/143와 유사한 문제이다. 두 문자열 사이에 더미를 끼운 뒤 하나로 연결한 후 LCP Array의 최댓값을 구하는데 이때 해당 LCP[i]를 구성하는 SA[i]와 SA[i-1]이 서로 다른 문자열에서 파생된 문자여야 한다. 거기에 해당 부분 문자열을 출력해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include #include #include #define MAX_N 200020using namespace std;char str[2.. 더보기 BOJ)5582 공통 부분 문자열 문제: icpc.me/5582 두 문자열이 주어질 때 공통 부분 문자열의 최대 길이를 출력하는 문제이다. 두 문자열 사이에 나올 수 없는 한 문자열을 더미로 끼운 뒤 두 문자열을 연결하여 (ex ABC!BCD) Suffix Array를 이용하여 LCP Array를 구할 때 비교 되는 접미사 SA[i]와 SA[i-1]가 서로 다른 문자열로부터 파생된 것들 중 LCP의 최대길이를 출력하면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #include #include #define MAX_N 10000using namespace st.. 더보기 BOJ)1605 반복 부분문자열 문제: icpc.me/1605 한 문자열의 부분문자열 중에서 두번 이상 나타나는 문자열 중에 가장 긴 문자열의 길이를 출력하는 문제이다. Suffix Array를 이용하여 LCP Array를 구해준 뒤 LCP Array중 최댓값이 두번 이상 나타나는 문자열 중 가장 긴 문자열이다. 한 부분 문자열이 두번 이상 출현한다면 이를 접두사를 갖는 접미사들은 접미사 배열상에서 항상 인접해 있기 때문이다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #include #include #define MAX_N 200020using namespace std;char .. 더보기 Suffix Array & LCP Array(Longest Common Prefix Array) Suffix Array는 번역하면 접미사 배열으로 다양한 문자열 문제들을 해결할 수 있는 매우 강력한 자료구조 입니다. Suffix Array는 문자열의 Suffix를 사전순으로 정렬한 배열입니다. 예를 들어 banana라는 문자가 있다면 Suffix Array는 다음과 같이 됩니다. 하지만 Suffix Array를 이렇게 문자열로 가지고 있을 경우 O(N^2)의 공간 복잡도를 가지게 될 것입니다. 그렇기 때문에 Suffix Array는 몇번째 접미사인지 나타내는 정수 i만 가지는 정수형 자료 구조형태를 가집니다. 다음과 같이 말이죠. 자 이제 Suffix Array의 정의에 대해 알았으니 구현을 해 볼 차례입니다. 단순하게 접미사 배열을 구한다면 접미사를 구한다음 정렬을 하는 방법이 있겠군요 하지만 이.. 더보기 이전 1 다음
