robustflame의 블로그

문제링크 - http://codeforces.com/contest/777/problem/D문제 분류난이도 - 중태그 - greedy, strings문제 풀이주어진 문자열들의 접미사들을 최소한으로 없애서 모든 문자열들이 사전순으로 정렬되어 있도록 하는 문제다. 연속된 두 문자열이 사전 순서로 되어야만 하므로, 두 문자열이 순서가 올바르지 않을때 무언가 조치를 취해야 한다. 다음과 같이 두 문자열의 순서가 잘못되었다고 해보자. # a b d ..# a b c .. 접미사를 없애야 하는데, 두 번째 문자열의 접미사를 어떻게 없애더라도 사전상으로 올바르게 할 수 없다. 무조건 첫 번째를 없애야 한다. 연속적인 두 문자열에 대해서 이렇기 때문에 모든 문자열에 대해서 확장해보면 가장 마지막 문자열부터 바로 이전 문..

Suffix Array 접미사 배열(suffix array)는 어떤 문자열 S의 모든 접미사를 사전순으로 정렬해둔 것으로, 보통 각 접미사의 시작 위치를 저장하는 정수 배열로 구현된다. 길이가 \(n\)인 문자열의 접미사 배열을 만드는 가장 빠른 알고리즘은 \(O(N)\)만에 접미사 배열을 만든다고 한다. 하지만 프로그래밍 대회에서는 이 복잡한 알고리즘을 직접 구현하여 사용하기에는 어려워 보통 그 대안으로 적당히 구현하기 쉽고, 적당히 빠른 알고리즘을 대신 사용한다. 접미사 배열을 만드는 \(O(N{log_2}^2N)\) 알고리즘은 각 접미사를 첫 한 글자로 정렬하고, 그 다음에 두 글자, 네 글자.. 로 \(log_2N\) 번 정렬하는 것이다. 각 접미사들이 서로 완전히 다른 문자열들이 아니라 두 접미..

Knuth-Morris-Pratt Pattern Searching 긴 문자열 \(A\)(길이 \(M\))에서 특정 패턴 문자열 \(B\)(길이 \(N\))가 나타나는 모든 위치를 \(O(M + N)\) 시간에 찾아내는 알고리즘이다. 구현#include using namespace std; // 문자열 A에서 문자열 B와 일치하는 위치를 모두 찾는다. vector KMPSearch(const string& A, const string& B) { int AN = A.length(), BN = B.length(); // 부분 일치 테이블 생성 vector pi(BN, 0); int matched = 0; for (int i = 1; i 0 && B[i] !..