본문 바로가기

KMP

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)13506 카멜레온 부분 문자열 문제: icpc.me/13506 접두사와 접미사가 동시에 될 수 있는 최대 부분 문자열 중 접두사와 접미사가 둘다 아니게도 등장하는 부분 문자열을 카멜레온 부분 문자열이라고 할 때 카멜레온 부분 문자열중에서 가장 길이가 긴 부분 문자열을 출력하는 문제이다. KMP의 pi배열을 이용한다면 우리는 prefix와 suffix를 동시에 만족시키는 모든 문자열의 길이를 알 수 있다 // pi[l] -> pi[pi[l]] ->pi[pi[pi[l]]] ... 이 때 prefix와 suffix를 둘 다 만족안하게 등장하는 경우는 pi[0]과 pi[length]를 제외하고 현재 확인하는 부분문자열의 길이와 같은 pi[x]가 존재하는 경우이다. 1234567891011121314151617181920212223242526.. 더보기
BOJ)10266 시계 사진들 문제: icpc.me/10266 각 시계의 바늘들을 1 빈 공간을 0으로 표시해준 뒤 환형 문자열 A에서 B를 탐색하여 존재하는 경우 possible을 출력하면 된다. 환형 문자열 A를 탐색하는 방법은 A 2개를 이어붙인 문자열에서 B를 탐색하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include #include #include #define N 360000using namespace std;int n, f, t;bool arr[720100];bool brr[360100];int pi[360100];void getpi(){ int j = 0; for (int i.. 더보기
BOJ)1305 광고 문제:icpc.me/1305 광고의 길이중 가장 짧은 광고는 조금만 생각해보면 n-pi[n-1]이라는 걸 알 수 있다. 123456789101112131415161718192021222324252627#include #include #include #include #include using namespace std;vector pi;int n;string x;void getpi(){ int j = 0; for (int i = 1; i 0 && x[i] != x[j]) j = pi[j - 1]; if (x[i] == x[j]) pi[i] = ++j; }}int main(){ scanf("%d", &n); pi.resize(n + 1); cin >> x; getpi(); printf("%d\n", n - p.. 더보기
BOJ)1893 시저 암호 문제: icpc.me/1893 문자열 W가 주어질 때 W를 A의 조건에 맞게 쉬프트하여 문자열 S에서 n번 만큼 쉬프트한 W가 1개일 경우 답에 추가하는 문제이다. A의 조건의 순서를 dictionary를 이용하여 인덱스로 관리해주고 W를 한번씩 쉬프트 해주면서 S에서 W를 KMP를 이용하여 검색하였을 때 1번만 검색되는 경우만 출력해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475#include #include #include #include #include #include using na.. 더보기
KMP(Knuth–Morris–Pratt) 알고리즘 KMP 알고리즘은 문자열 A와 문자열 B가 있을 때, 문자열 A에서 문자열 B를 찾아주는 알고리즘 입니다. KMP는 KMP를 만든 사람의 이름인 Knuth, Morris, Prett 세 사람의 앞 글자를 따서 KMP 알고리즘이라고 불립니다. 자 그러면 우리는 문자열 A에서 문자열 B를 찾는 방법을 생각해봅시다. 가장 먼저 생각해 볼 수 있는 방법은 Brute force가 있겠군요. 하지만 모든 경우를 다 탐색할 경우 문자열 A의 길이가 N,문자열 B의 길이가 M이라면 O(N*M)의 시간 복잡도를 가지게 됩니다. 만약 N,M이 10만인 문제가 주어진다면 시간 초과를 보게 될 것입니다. 자 그러면 KMP를 사용하였을 때의 시간복잡도는 어떻게 될까요? 놀랍게도 O(N+M)의 시간복잡도만에 문자열 A에서 문자열.. 더보기
BOJ)1701 Cubeditor 문제: icpc.me/1701 문자열이 주어질 때 2번이상 나오는 부분 문자열 중 가장 길이가 긴 부분 문자열의 길이를 출력하는 문제이다. N이 5000밖에 안되기 때문에 문자열의 모든 Suffix에 대해서 failure function을 구해준 뒤 그 중 최댓값을 출력하면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include #define MAX_N 5001using namespace std;char a[MAX_N][MAX_N];int l, r;vector pi;void getpi(const char *c,int len) { pi.clear(); pi.resize(len); .. 더보기
BOJ)11585 속타는 저녁 메뉴 문제: icpc.me/11585 문자열 A와 B가 주어질 때 환형으로 이루어진 문자열 B로 이루어진 돌림판을 돌려서 A가 나올 확률을 구하는 문제이다. 우리는 환형으로 이루어진 문자열 B를 구현하기 위하여 문자열 B뒤에 문자열 B를 붙인 뒤 KMP를 이용하여 2개의 연속 된 문자열 B에서 A를 찾는 횟수를 구한 뒤 기약 분수 형태로 만들어 출력해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #include #define MAX_N 1000000using namespace std;char a[MAX_N], b[2 * MAX_N];int n,.. 더보기
BOJ)4354 문자열 제곱 문제: icpc.me/4354 문자열 A가 주어질 때, A를 서로 같은 부분 문자열 N개로 쪼갤 수있을 때 N의 최댓값을 출력하는 문제다. 우리는 문자열이 N개의 부분 문자열로 쪼개질 때 규칙성을 찾아보면 KMP에서의 pi배열의 pi[a.length()-1]=(n-1/n)*a.length()를 만족한다는 걸 알 수 있다. 이를 이용하여 최대 N을 계산해주면 된다. 12345678910111213141516171819202122232425262728293031323334#include #include #include #include #include using namespace std;string a;vector pi;void getpi(){ pi.clear(); pi.resize(a.length()); i.. 더보기
BOJ)2401 최대 문자열 붙여넣기 문제 : icpc.me/2401 긴 문자열에 여러개의 짧은 문자열을 붙일 때 얼마만큼 붙일 수 있는지 최대 길이를 출력하는 문제이다. KMP로 긴문자열에 대응하는 짧은 문자열들을 찾아주어 (a부터b까지 짧은 문자열이 같다면) a 점에서 붙일 수 있는 점들을 vt[a]에 b로 저장 해 준 후 다이나믹 프로그래밍을 이용하여 답을 구해준다 . dp테이블의 정의는 dp[x]는 x번째 문자열부터 시작하였을 때 붙일 수 있는 문자열의 최대 길이이다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include #inc.. 더보기

티스토리툴바