공작소

문제 링크 : https://www.acmicpc.net/problem/27504 문제상대음감은 음을 절대적인 높이로 구분하는 것이 아닌 어떤 음과의 상대적인 높이로 음을 인식하는 능력을 말한다. 상대음감은 절대음감에 비해 불리한 점이 있지만, 노래를 찾을 때 어렴풋한 멜로디 만으로도 노래를 찾을 수 있다는 장점이 있다.기령이는 이러한 점에서 착안하여 상대음감의 노래찾기 서비스를 만들려고 한다. 노래찾기 서비스는 데이터베이스에 노래의 음 데이터를 갖고 있으며 사용자가 멜로디를 입력했을 때 그 멜로디가 데이터베이스의 노래에 포함되어 있으면 해당 노래를 안내해 주는 서비스이다. 상대음감의 노래찾기 서비스는 상대적인 멜로디가 포함되어 있어도 일치하는 것으로 판단해 노래를 안내해준다. 즉, 찾으려는 멜로디가 a..

문제 링크 : https://www.acmicpc.net/problem/3779 문제아스키 코드가 97이상 126이하인 N개의 문자로 이루어진 문자열 S가 주어진다. 문자열 S의 모든 접두사에 대해, 각각의 접두사가 주기적인 문자열인지 아닌지 알고 싶다. 다시 말해 2 ≤ i ≤ N을 만족하는 각각의 i에 대해, 길이가 i인 문자열 S의 접두사가 어떤 문자열 A에 대해 AK 형태로 표현할 수 있는 가장 큰 K > 1을 알아내려 한다.AK란 문자열 A가 K번 연속되어있는 문자열을 의미한다. A = "abad"이고, K = 3인 경우 AK = "abadabadabad"이다.입력입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 두 줄로 이루어진다. 테스트 케이스의 첫 번째 줄에는 문자열 S의 ..

문제 링크 : https://www.acmicpc.net/problem/1498 문제어떤 문자열 X를 n번 연달아 쓴 것을 (X)^n으로 나타내기로 하자. 예를 들어 (ab)^3는 ababab를 의미한다. 어떤 문자열 Y가 (X)^n 꼴로 표현될 수 있다면, 그리고 n이 1이 아니라면 Y를 주기문 이라고 한다. 예를 들어 ab는 주기문이 아니지만, abab는 (ab)^2으로 표현할 수 있으므로 주기문이 된다.문자열 S(2 ≤ S의 길이 ≤ 1,000,000)가 주어졌을 때, S의 앞에서부터 i개의 문자가 주기문의 형태가 되는 경우를 찾으려 한다. 가능한 경우가 여럿일 경우에는 n이 최대가 되는 경우를 구하려고 한다. S는 알파벳 소문자로만 이루어져 있다.문자열 S가 주어졌을 때, 가능한 i, n 쌍을 모..

문제 링크 : https://www.acmicpc.net/problem/3356 문제라디오 방송국은 메시지를 여러 청취자에게 전송한다. 모든 청취자가 메시지를 확실히 받게 하기 위해서 메시지를 계속해서 반복 전송한다.한 청취자가 받은 메시지가 주어진다. 항상 청취자가 받은 메시지의 길이는 방송국에서 보낸 메시지의 길이보다 크거나 같다. 이때, 라디오 방송국에서 보낸 메시지를 구하는 프로그램을 작성하시오.즉, 입력으로 S가 주어졌을 때, S가 S' + S' + ... + S'의 부분 문자열이 되는 가장 짧은 부분수열 S'를 구하는 프로그램을 작성하시오. 입력첫째 줄에 S의 길이 L이 주어진다. 둘째 줄에는 길이가 L인 S가 주어진다. 메시지는 알파벳 소문자로만 이루어져 있다. (1 ≤ L ≤ 1,000,0..

문제 링크 : https://www.acmicpc.net/problem/13506 문제문자열 S의 부분 문자열 T 중에서, 접두사(Prefix)도 될 수 있고, 접미사(Prefix)도 될 수 있고, 두 경우가 아닌 위치에도 등장하는 T를 카멜레온 부분 문자열이라고 한다.문자열 S가 주어졌을 때, 카멜레온 부분 문자열을 구하는 프로그램을 작성하시오.예를 들어, S = "fixprefixsuffix"와 같은 경우에는 "fix"는 접두사, 접미사도 되고, 두 경우가 아닌 위치에도 등장하는 부분 문자열로도 등장한다.입력첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져있으며, 길이는 106을 넘지 않는 자연수이다.출력가능한 카멜레온 부분 문자열 T 중에서 길이가 가장 긴 것을 출력한다. 만약, T..

문제 링크 : https://www.acmicpc.net/problem/1305 문제세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다.전광판에는 같은 내용의 문구가 무한히 반복되어 나온다. 또, 전광판의 크기는 전광판에서 한번에 보이는 최대 문자수를 나타낸다. 만약 전광판의 크기가 L이라면, 한번에 L개의 문자를 표시할 수 있는 것이다.광고업자는 최대한의 광고효과를 내기 위해서 길이가 N인 광고를 무한히 붙여서 광고한다.예를 들어, 광고 업자 백은진이 광고하고 싶은 내용이 aaba 이고, 전광판의 크기가 6이라면 맨 처음에 보이는 내용은 aabaaa 이다. 시간이 1초가 지날 때마..

커누스-모리스-프랫 알고리즘 (Knuth–Morris–Pratt algorithm, KMP) 은 문자열 S 에서 문자열 A 를 찾고자 할 때 단순히 모든 경우를 다 비교해보면서 찾는 방식 보다는 접두사와 접미사를 이용해 불필요한 문자열 탐색 횟수를 줄여 문자열을 효율적으로 찾아낼 수 있는 문자열 매칭 알고리즘이다. 하나씩 비교하는 문자열 매칭문자열 S의 길이를 N, 문자열 A의 길이를 M이라 할 때, 문자열 S 에서 문자열 A를 찾을 때의 시간 복잡도는 O(NM) 이다.S = input()A = input()for i in range(len(S)): for j in range(len(A)): if S[i+j] != A[j]: break if j == len(A) - 1: print(i)# I..