문자열

[백준 4354] 문자열 제곱 (C++)

4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net KMP 예를 들어 문자열 abcab가 있다고 하자 kmp알고리즘을 사용해서 주어지는 문자열마다 접두사 실패 table을 만들어 준다. -> {0, 0, 0, 1, 2} table의 마지막 수는 마지막으로 접두사와 중복되는 문자열의 길이를 의미한다. -> 2 (ab 중복) 현재 문자열(text)의 크기에서 마지막으로 중복되는 접두사의 길이를 빼준다. -> 5 - 2 = 3 위 값은 중요하다. 무엇을 의미하는 걸까? 값 '3'은 ..

[백준 1701] Cubeditor (C++)

1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net KMP 문자열의 길이가 5,000이라서 O(N^2) 시간이 가능하다. kmp알고리즘은 text문자열과 pattern문자열이 주어지고, pattern문자열에서 text 문자열의 접두사가 몇 번 나오는지, 나올때마다 접두사의 몇 번째 문자열까지 나오는지 알 수 있다. text문자열을 pattern으로 써서 일명 jump table 이라고 하는걸 만들 수 있는데 jump table의 특성을 생각해보면 문제를 해결할 수 있다. 위 ..

[백준 1305] 광고 C++

1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광 www.acmicpc.net KMP 15분 정도 뚫어져라 본 결과 규칙을 찾았다. 문자열의 마지막이 접두사와 중복된 채로 끝난다면 해당 중복 문자열의 길이만큼 광고 문자열을 감소시킬 수 있다. babba 라는 문자열이 주어졌다고 가정. 접두사 table을 만들어보자 table = {0, 0, 1, 1, 2} 테이블의 마지막 값이 2이므로 해당 문자열은 마지막 2개가 중복된다고 볼 수 있다. 따라서 문자열의 길이 5에서 중복 문자열 2개를 제외한 3개가 답이 된다. -> bab 다음 광고가 중복되는 부분부터 ..

[백준 1786] 찾기 C++

1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net KMP 어젯밤부터 이해하는데 어려움을 느꼈던 알고리즘 기본 kmp문제를 보니 대놓고 알고리즘을 설명해주고 있다. 더보기 워드프로세서 등을 사용하는 도중에 찾기 기능을 이용해 본 일이 있을 것이다. 이 기능을 여러분이 실제로 구현해 보도록 하자. 두 개의 문자열 P와 T에 대해, 문자열 P가 문자열 T 중간에 몇 번, 어느 위치에서 나타나는지 알아내는 문제를 '문자열 매칭'이라고 한다. 워드프로세서의 찾기 기능은 이 문자열 매칭 문제를 풀어주는 기능이라고 할..