본문 바로가기

KMP

 (6)
[백준 / BOJ] 1498 주기문 문제 출처 : https://www.acmicpc.net/problem/1498 1498번: 주기문 어떤 문자열 X를 n번 연달아 쓴 것을 (X)^n으로 나타내기로 하자. 예를 들어 (ab)^3는 ababab를 의미한다. 어떤 문자열 Y가 (X)^n 꼴로 표현될 수 있다면, 그리고 n이 1이 아니라면 Y를 주기문 이라고 한다 www.acmicpc.net 어떤 문자열 X를 n번 연달아 쓴 것을 X^n으로 나타낸다. 예를들어, 문자열, ababab는 ab^3이 된다. 문자열 X를 앞에서부터 i번째까지 주기문을 이룬다고 했을때, 해당 주기문의 n(n은 가능한 가장 크게)을 구하는 문제다. 예를들어, 문자열 abababab는 4 2 6 3 8 4 가 출력된다. 풀이 kmp로 푸는 문제였다. 주기를 찾는다는것은 ..
[백준 / BOJ] 1097 마법의 단어 문제 출처 : https://www.acmicpc.net/problem/1097 1097번: 마법의 단어 첫째 줄에 단어의 개수 N이 주어진다. N은 8보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 단어가 주어진다. 단어의 길이는 최대 20이다. 단어는 알파벳 대문자로만 이루어져 있다. 마 www.acmicpc.net N개의 단어가 있다. N개의 단어를 적절히 조합하여 (이때, N개의 단어를 전부 사용해 조합해야한다) 문자열 T를 만든다. 문자열 T의 시작지점을 i만큼 오른쪽으로 이동시켰을때 문자열을 T(i)라 한다. (문자열 ABCD를 오른쪽으로 2만큼 움직인후 문자열은 CDAB가 된다.) 이때, 문자열 T와 바뀐문자열 T(i)가 정확히 일치하게되는 i가 k개 있으면, 이 문자열을 "마법의..
[백준 / BOJ] 16916 부분 문자열 (Java) 문제 출처 : https://www.acmicpc.net/problem/16916 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 문자열 S, 문자열 P가 주어진다. 문자열 P가 문자열 S에 속하는지 확인하는 문제다. 풀이 KMP알고리즘을 이용해 푸는 문제다. 문자열의 길이가 최대 100만까지 증가하기때문에, KMP알고리즘을 이용해 풀어야한다. (suffix배열을 만들지 못하는 문자열에서 여전히 시간초과가 나올것이라 생각했는데, 다행히? 그런 테스트케이스는 없는것 같다.) 로직 1. 문자열 P가 S에 포함되는지 확인해야하기 때문에, 문자..
[백준 / BOJ] 1305 광고 문제 출처 : https://www.acmicpc.net/problem/1305 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광 www.acmicpc.net 세준이는 길 한가운데에서 전광판을 보고있다. 전광판에는 광고가 나오고있다. 전광판의 크기는 전광판에서 한번에 보이는 문자열의 최대 길이를 나타낸다. 전광판의 크기 L과 세준이가 본 전광판의 글자가 주어졌을때, 가능한 광고길이중 최솟값을 출력하는 문제다. 풀이 모든경우를 보면, L^2이 되서 시간안에 통과하지못한다. KMP알고리즘을 이용해 푼문제다. 광고판에서 광고가 나올수있는 경우는 광고 A뒤에 똑같..
[백준 / BOJ] 13506 카멜레온 부분 문자열 문제 출처 : www.acmicpc.net/problem/13506 13506번: 카멜레온 부분 문자열 문자열 S의 부분 문자열 T 중에서, 접두사(Prefix)도 될 수 있고, 접미사(Prefix)도 될 수 있고, 두 경우가 아닌 위치에도 등장하는 T를 카멜레온 부분 문자열이라고 한다. 문자열 S가 주어졌을 때, 카 www.acmicpc.net 카멜레온 부분 문자열이란, 문자열 S의 접미사이자 접두사인 부분문자열 T가 문자열S에서 한번 더 나오는 문자열을 말한다. 예를들어, fixprefixsuffix에서 fix는 카멜레온 부분문자열인데, fix가 접두사, 접미사, 그리고 중간에 한번 더 나오기때문이다. 마찬가지로 abcabcabc또한 카멜레온 부분문자열이다. 문자열 S가 주어졌을때, 가장 긴 카멜레온..
[백준 / BOJ] 1701 Cubeditor 문제 출처 : www.acmicpc.net/problem/1701 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net Cubelover는 텍스트 에디터 Cubeditor를 만들었다. 이 에디터가 다른 에디터와 다른점은, 찾을려하는 문자열이 2번이상 존재해야지 찾는것이다. 예를들어, ababac에서 aba를 찾을려하면 ababac 이렇게 찾을수있다. c를 찾을려하면 c는 한번밖에 나오지 못하므로 찾지못한다. 풀이 완전탐색으로 풀려할경우, 약 5000^3 반복할수있어서 시간초과가..

티스토리툴바