전체 string = S+"0"+T로 한 뒤 suffix arrary와 lcp array를 구하고 lcp배열 중 suffix[i], suffix[i-1]이 한쪽이 S이고 한쪽이 T인 경우 중에서만 최댓값을 갱신해 답을 구했습니다.
이것이 전체 string의 suffix들 중의 lcp를 구할 수 있다는 것은 이해가 되는데, lcp array는 정렬된 suffix array에서 인접한 suffix들끼리의 lcp들만 구하는데도 답이 나오는 것이 이해가 되지 않습니다. 그러니까 문제에서 원하는 답은 S와 T끼리의 lcp이니, 많이 겹치더라도 S와 T 내부에 사전상으로 더 가까운 suffix가 각각 있다면 전체 string의 suffix array상에서 떨어져 있을 수 있을 것도 같습니다.
이런 경우가 없다는 사실을 어떻게 알 수 있나요? 일단 proved by AC로 넘어가도 되는건지 반례가 있는건지라도 알려주시면 감사하겠습니다.
slah007 2년 전
전체 string = S+"0"+T로 한 뒤 suffix arrary와 lcp array를 구하고 lcp배열 중 suffix[i], suffix[i-1]이 한쪽이 S이고 한쪽이 T인 경우 중에서만 최댓값을 갱신해 답을 구했습니다.
이것이 전체 string의 suffix들 중의 lcp를 구할 수 있다는 것은 이해가 되는데, lcp array는 정렬된 suffix array에서 인접한 suffix들끼리의 lcp들만 구하는데도 답이 나오는 것이 이해가 되지 않습니다. 그러니까 문제에서 원하는 답은 S와 T끼리의 lcp이니, 많이 겹치더라도 S와 T 내부에 사전상으로 더 가까운 suffix가 각각 있다면 전체 string의 suffix array상에서 떨어져 있을 수 있을 것도 같습니다.
이런 경우가 없다는 사실을 어떻게 알 수 있나요? 일단 proved by AC로 넘어가도 되는건지 반례가 있는건지라도 알려주시면 감사하겠습니다.