https://www.acmicpc.net/problem/1498 1498번: 주기문 어떤 문자열 X를 n번 연달아 쓴 것을 (X)^n으로 나타내기로 하자. 예를 들어 (ab)^3는 ababab를 의미한다. 어떤 문자열 Y가 (X)^n 꼴로 표현될 수 있다면, 그리고 n이 1이 아니라면 Y를 주기문 이라고 한다 www.acmicpc.net 실패함수의 응용의 응용 반복되는 가장 작은 문자열 == 문제에서 원하는 "주기문" 의 길이를 https://blog.koderpark.dev/263 백준 BOJ 1305 - 광고 @이화월백 이 골라준 태그 문제풀이 오늘의 태그는 KMP되시겠다 https://www.acmicpc.net/problem/1305 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 ..

KMP P2 자력솔 헉!!!! https://www.acmicpc.net/problem/2401 2401번: 최대 문자열 붙여넣기 어떤 긴 문자열이 주어지고 여러 개의 짧은 문자열들이 주어질때 이때 짧은 문자열을 긴 문자열에 붙여 넣을때 가장 길게 붙여 넣는 경우를 찾아라. 단 이때 짧은 문자열들끼리는 교차 할 수 없 www.acmicpc.net 일단 처음 보고 한 생각은 KMP를 쓰더라도 브루트포싱은 힘들겠구나 였다. 문자열을 중복으로 넣을수 있다는 점에서 완탐을 하면 확실하게 시간초과임이 와닿을듯? 근데 이 문제는 긴 문자열 S에 어떤 짧은 문자열 s를 매칭 시킬 때, 매칭된 위치가 k라고 하면 S의 [0,k) 까지의 범위는 해당 문자열을 붙여넣던 말던 항상 값이 변하지 않는다. 앞서 문자열을 붙여넣..

https://www.acmicpc.net/problem/16900 16900번: 이름 정하기 첫째 줄에 S와 K가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 500,000보다 작거나 같다. K는 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net fail 배열이 가지고 있는 값이 접두사와 접미사가 같아지는 최대 길이임을 이용하는 문제. 문자열 두개를 최대한 많이 겹쳐내면 전체 문자열의 길이가 가장 짧아지게 되기 때문에 가장 적극적으로 겹쳐내기 위해서 실패함수 값이 담긴 배열을 구해준다 가장 적극적으로 겹쳤을 때 전체 문자열의 길이는 (전혀 겹치지 않았을때의 최대 길이) - (겹쳐진 부분만큼의 길이) 이고 겹치지 않았을때의 최대 길이는 S.length() * K 로 ..

언제나와같이 돌아온 KMP 아주 티어 올리는 맛이 달달한 태그다 https://www.acmicpc.net/problem/1893 1893번: 시저 암호 암호학에서, 시저 암호(또는 시프트 암호, 시저 코드, 시저 시프트)는 가장 간단하면서 많이 알려진 암호화 기술 중 하나이다. "시저 암호"라는 이름은 비밀 통신을 위해 이 방법을 개발한 율리 www.acmicpc.net 지문이 이해하기 그리 쉽지 않은 편인데 간단히 요약해보자면 알파벳 순서 표 A를 보고 원문 W를 X칸 이동시키면서 변환한 뒤에, 암호화된 문자열 S에서 변환된 W가 한번만 등장한다면 이때 가능한 모든 X를 찾는 문제이다. 문제를 나눠서 생각해보자. 1. 순서표 A를 보고 W를 한칸씩 이동시키기. 알파벳과 숫자를 매칭시켜 주는 unord..

https://www.acmicpc.net/problem/13506 13506번: 카멜레온 부분 문자열 문자열 S의 부분 문자열 T 중에서, 접두사(Prefix)도 될 수 있고, 접미사(Prefix)도 될 수 있고, 두 경우가 아닌 위치에도 등장하는 T를 카멜레온 부분 문자열이라고 한다. 문자열 S가 주어졌을 때, 카 www.acmicpc.net 접두사와 접미사가 같으면서 세군데 이상에서 등장하는 부분문자열을 구하는 문제. 메모리초과와 시간초과 둘다 낭낭하게 받아본 문제 되시겠다 생각보다 제한이 빡빡하지 않나 하는 생각이 든다. 일단 문자열의 길이를 N이라 했을때 fail[N-1] 을 통해서 접두사와 접미사가 같은 최대 길이 부분문자열을 구할 수 있고, 이 부분문자열을 KMP를 돌려서 3개 이상 탐색되는..

KMP 연습문제 https://www.acmicpc.net/problem/1787 1787번: 문자열의 주기 예측 P8 = 6, P7 = 6, P6 = 4, P5 = 4, P4 = 2, P3 = 2, P2 = 0, P1 = 0 www.acmicpc.net 실패함수를 활용해 구한 값과 정확히 정반대를 요구하는 문제. 접두사와 접미사가 같아지는 최소 길이를 구해서 문자열의 전체 길이와 빼면 문제에서 요구하는 "추정할 수 있는 주기 중 가장 긴 것의 길이" 를 구할 수 있다. 실패함수에서 뒤로 돌아가고자 할때 j = fail[j-1]; 사용하는 이 구문에서 착안하고 while(dp[i] && fail[dp[i]-1]) dp[i] = fail[dp[i]-1]; 계속 뒤로 돌아가게끔 while문을 사용해서 작성해..

https://www.acmicpc.net/problem/7575 7575번: 바이러스 첫 번째 줄에는 감염된 프로그램의 개수 N 과 바이러스 코드 추정을 위한 최소 길이를 나타내는 정수 K 가 주어진다. 단, 2 ≤ N ≤ 100이고, 4 ≤ K ≤ 1,000이다. 두 번째 줄부터 각 프로그램에 대한 www.acmicpc.net KMP 3일차 그 두번째 문제 문제가 복잡하게 생겼는데 구현 자체는 그리 복잡하지는 않다. 입력되는 문자열 중 하나에서 길이가 K인 부분문자열 S'를 분리한 뒤, 다른 모든 문자열에 이 S' 이 포함되어있는지 세어주면 되는 문제이다. KMP 알고리즘을 적용하면 생각보다 나이브하게 풀리니까 부분문자열 분리하거나 할때 괜히 복잡하게 고민하지 말고 그냥 O(N)으로 분리해주도록 하자..

https://www.acmicpc.net/problem/1701 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net KMP를 뇌에 박기위한 연습 3일차 실패함수 배열을 활용하는 문제였다. 접두사와 접미사가 같아지는 최대 길이가 fail[k] 일때, 접두사와 접미사가 같아지면서 두번 이상 나오는 문자열의 조건을 충족하기 때문에, 실패함수 배열에서의 최대값이 문제에서 요구하는 정답이 된다. 접미사는 가변적으로 바뀔수 있는 반면 접두사는 문자열의 제일 앞을 항상 포함하고 있기 때..