목록SA (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
이전 Prev 1 Next 다음