- 단순 문자열 매칭
- KMP 알고리즘
- 라빈-카프 알고리즘
- 트라이 : 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
- 아호 코라식 (Aho-Corasick)
1. 단순 문자열 매칭
아래 블로그에 들어가보면, 단순 문자열 매칭에 대해 잘 설명해 놓았다.
https://blog.naver.com/ndb796/221240660061
30. KMP(Knuth-Morris-Pratt) 알고리즘
이번 시간에 다루게 될 알고리즘은 KMP 알고리즘으로 대표적인 문자열(String) 매칭 알고리즘입니다. ...
blog.naver.com
2. KMP 알고리즘
https://www.acmicpc.net/problem/1786
1786번: 찾기
첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m
www.acmicpc.net
https://www.acmicpc.net/problem/1305
1305번: 광고
세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광
www.acmicpc.net
https://www.acmicpc.net/problem/4354
4354번: 문자열 제곱
알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다
www.acmicpc.net
https://www.acmicpc.net/problem/11585
11585번: 속타는 저녁 메뉴
수원이와 친구들은 저녁 메뉴를 잘 선택하지 못한다. 배가 고픈 수원이가 보다 못해 메뉴를 정하곤 하는데 이마저도 반대에 부딪히는 경우에는 수원이가 원형 룰렛을 돌려 결정하곤 한다. 이 원
www.acmicpc.net
3. 라빈-카프 알고리즘
https://www.acmicpc.net/problem/1786
1786번: 찾기
첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m
www.acmicpc.net
4. 트라이
https://www.acmicpc.net/problem/14425
14425번: 문자열 집합
첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어
www.acmicpc.net
https://www.acmicpc.net/problem/5052
5052번: 전화번호 목록
첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가
www.acmicpc.net
https://www.acmicpc.net/problem/5670
5670번: 휴대폰 자판
휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발
www.acmicpc.net
5. 아호 코라식 (Aho-Corasick)
https://www.acmicpc.net/problem/9250
9250번: 문자열 집합 판별
집합 S는 크기가 N이고, 원소가 문자열인 집합이다. Q개의 문자열이 주어졌을 때, 각 문자열의 부분 문자열이 집합 S에 있는지 판별하는 프로그램을 작성하시오. 문자열의 여러 부분 문자열 중 하
www.acmicpc.net
https://www.acmicpc.net/problem/10256
10256번: 돌연변이
인간의 DNA 구조는 A, C, G, T로 이루어진 하나의 긴 문자열로 표현할 수 있다. 이때, 몇 몇 질병은 DNA 구조를 나타낸 문자열의 어떤 연속된 부분 문자열과 관련이 있다는 것이 밝혀져 있다. 만일 DNA
www.acmicpc.net
'자료구조 + 알고리즘' 카테고리의 다른 글
| LIS (Longest Increasing Subsequence, 최장 증가 부분수열) (0) | 2021.09.14 |
|---|---|
| LCA (Lowest Common Ancestor, 최소공통조상) (0) | 2021.09.14 |
| 최소비용 최대유량 알고리즘 (0) | 2021.09.14 |
| 이분매칭 (Bipartite Matching) (0) | 2021.09.14 |
| SCC (강결합요소) (0) | 2021.09.14 |