일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- lcp
- 유량
- 이분탐색
- 티스토리챌린지
- 트리dp
- Segment tree
- Seg
- 2SAT
- 아호코라식
- spfa
- 임대차계약
- 디닉
- 투룸
- MCMF
- SCC
- 접미사배열
- treedp
- TRIE
- suffix array
- 구현
- 오블완
- dinic
- LCA
- 전월세
- 월세
- 2-sat
- 좌표압축
- 이분매칭
- 세그먼트트리
- 트라이
Archives
- Today
- Total
목록접미사배열 (1)
N coding
13576_Prefix와 Suffix
해야 하는 것 1. 접두사 == 접미사인 애들의 길이를 찾는다.2. 걔네가 몇 번 나오는지 찾는다. 내가 문자열과 쿼리를 푼 방법으로 찾았다. 접두사 == 접미사이려면 suffix array를 구했을 때, 1. 원본 문자열과 lcp가 존재해야하고, 그 lcp의 길이가 자기 자신의 길이와 같아야한다.2. 그리고 그 cnt는 원본 문자열과 자기 자신의 sa상에서 떨어진 거리이다. sfx상에서 원본 문자열보다 위쪽에 있는 애들은 그냥 구해주면 된다.아래쪽에 있는 애들도 그냥 구해주면 된다.다만 위쪽에 있는 애들이 아래쪽에도 계속 공통으로 나올 수 있고그 한계는 자신의 길이보다 짧은 lcp가 나올때 이므로 minn값이 바뀔때마다그 minn길이의 ans가 있는 지 확인한 후 있으면 cnt를 넣어주었다.더해줄때 하..
PS
2018. 8. 31. 18:46