1787 - 문자열의 주기 예측
문제 링크 https://www.acmicpc.net/problem/1787 문제 요약 문제가 이해를 하기 조금 힘들지만 결국 하는말은 다음과 같다. 어떠한 문자열 \(X\)가 있다고 가정을 하자. 이 때 \(X\)의 \(Prefix\)와 \(Suffix\)를 구하는데 이 때 빈 문자열이면 안되고 서로 동일한 길이여야 한다. 이렇게 뽑았을 때 \(Prefix\)와 \(Suffix\)가 같은 0이 아닌 가장 작은 길이를 구한다음에 \(X\)의 길이에서 뺀뒤 이 값을 답에 누적한다. 이러한 과정을 문자열 \(S\)가 주어지면 \(S\)의 모든 \(Prefix\)에 대해서 반복한다. 문제 풀이 주어지는 문자열 \(S\)의 길이가 \(10^6\)이기 때문에 빠른 풀이를 생각해야 한다. 결론부터 얘기하면 이 문제..
Problem/BOJ
2016. 11. 10. 13:10
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- Sqrt Decomposition
- Binary Search
- bipartite matching
- brute force
- disjoint set
- max flow
- greedy
- graph
- DP
- Data Structure
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
글 보관함