devbelly

문제 https://www.acmicpc.net/problem/9249 알고리즘 Suffix Array 풀이 LCS문제입니다. 주어진 두 문자열$A, B$를 합친 후 LCP를 구하게 되면 답을 얻을 수 있습니다. 이때 주의해야 할 점이 있습니다. 인접한 LCP를 검사할 때, 하나의 Suffix는 $A$의 일부를 포함해야 하지만, 나머지 Suffix는 $A$를 포함해선 안된다는 점입니다. 이점을 유의하지 않으면 $A$ 또는 $B$ 내에서만 LCP를 뽑아버리므로 두 문자열의 공통부분 문자열을 얻지 못하게 됩니다. 시간 복잡도는 Suffix Array와 LCP를 구해야 하므로 $O(NlogN+N)$입니다. 코드 #include #define rep(i,n) for(int i=0;i