platinant

문제 알파벳 소문자로만 이루어진 문자열이 주어진다. 부분문자열의 "등장값" 이란 그 부분문자열이 등장하는 횟수와 부분문자열의 길이를 곱한 값이다. 문자열이 주어졌을 때, 팰린드롬이면서 가장 큰 등장값을 가지는 부분문자열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 알파벳 소문자(a-z)로만 이루어진 문자열이 주어진다. 문자열의 길이는 300,000보다 작거나 같다. 출력 첫째 줄에 팰린드롬인 부분문자열 중에서 가장 큰 등장값을 출력한다. 예제 입력 abacaba 예제 출력 7 풀이 이 문제는 접미사 배열과 lcp, manacher 알고리즘을 모두 사용하는 문제이다. 어떤 자료구조를 사용하느냐에 따라 시간복잡도가 $\BigO{N\log^{2}N}$이 되기도 하고, $\BigO{N\log{N}}$이 되기..

길이 N인 문자열의 접미사 N개를 사전 순으로 정렬해 놓은 배열을 접미사 배열이라고 한다. 접미사 배열에 문자열을 저장하면 메모리가 $\BigO{N^2}$만큼 필요한데 이는 심각한 낭비이다. N개의 접미사에 시작 위치를 기준으로 0부터 N-1까지 번호를 붙일 수 있으므로 이 번호를 저장하자. 그러면 접미사 배열을 $\BigO{N}$의 메모리로 나타낼 수 있다. 접미사 배열은 중복되는 부분문자열을 찾기에 유용하다. "mississipi"라는 문자열에서는 "issi"가 두 번 반복된다. "issi"처럼 부분문자열이면서 중복되는 문자열들을 찾고 싶으면 어떻게 하면 될까? 접미사 배열이 사전순으로 정렬되어 있다는 것을 이용해보자. 일단 부분문자열들은 모두 어떤 접미사의 접두사일 것이다. 접미사 배열에서 앞부분들..

팰린드롬은 앞으로 읽으나 뒤로 읽으나 똑같은 문자열을 말한다. 문자열 문제에서 자주 등장하는 개념이다. 주어진 문자열의 부분 문자열에서 가장 긴 팰린드롬을 쉽게 찾을 수 있는 $\BigO{N}$알고리즘이 존재한다. Manacher's Algorithm이라고 하는데 코드도 짧고 이해하기도 쉬워서 한 번 알아두면 유용하게 사용할 수 있다. 먼저 팰린드롬을 구할 때는 길이가 홀수인 팰린드롬과 짝수인 팰린드롬을 따로 생각해야 한다. 이것이 좀 골치 아프므로 한 가지 트릭을 사용하는데 주어진 문자열에서 문자 사이사이마다 더미 문자를 집어넣는 것이다. 예를 들어, "ababa"에서 팰린드롬을 찾는다고 하면 문자열을 "#a#b#a#b#a#"로 바꾸는 것이다. 이제 각 i에 대해서 S(i-x,i]=S[i,i+x)인 x..

KMP가 긴 문자열에 어떤 짧은 문자열 하나가 몇 번 나타나는지 검색하는 알고리즘이었다면 AhoCorasick은 여러 개의 짧은 문자열들이 몇 번 나타나는지 검색하는 알고리즘이다. 여러 문자열이 얼마나 나타나는지 KMP를 사용해 확인하려면 (문자열의 개수)\(\times\)(문자열의 길이)만큼의 시간이 걸릴 텐데 AhoCorasick을 사용하면 선형시간만에 해결할 수 있다. 먼저 트라이라는 자료구조를 알아야 한다. 트라이는 문자를 간선으로 사용하는 트리인데 루트에서 아래로 내려가면서 문자열을 검색할 수 있다. 다음 그림을 보자. 트라이에 a,ba,bab,bc 네 문자열을 넣은 상태이다. 각 문자열의 마지막 노드를 회색으로 칠해 놓았다. 이렇게 여러 문자열을 저장해두면 특정 문자열이 존재하는지 선형시간 만..

KMP는 길이가 긴 문자열에서 어떤 짧은 문자열이 몇 번 나타나는지 선형시간에 확인할 수 있는 알고리즘이다. 0부터 i번째 까지 맞고 i+1번째에서 틀렸다면 0부터 i번째 까지 맞았다는 정보를 이용하여 탐색을 개선할 수 있다. 다음 그림을 보자. abcab까지는 맞지만 c와 x가 다르다. 이때 여태까지 맞은 abcab를 잘 보자. abcab에서 접두사면서 접미사인 최대 길이 문자열은 ab이다. 이제 밑의 문자열을 오른쪽으로 세칸 움직여서 ab를 일치시킨 후 탐색을 재개하면 된다. 이렇게 하면 위의 문자열에서 문자를 보는 위치가 감소하지 않고 계속 증가하기 때문에 수행시간이 빨라진다. 이를 위해 구해야 하는 것이 실패함수이다. fail[i]는 문자열 S의 부분 문자열인 S[0,i]에서 접두사이면서 접미사인..