BOJ 13012 - 접미사 배열 1

BOJ 13012 - 접미사 배열 1

이전에 못풀었던 문제같은데, 다시 풀어보았다.

단 $T < S$ 이므로 $T$는 어떤 문자가 $S$보다 작다.

그럼 그냥 $S$ 중에 $a$ 가 아닌 문자 중 하나만 $-1$ 을 해주고 suffix array를 구성해서 같은지 확인하면 되지 않을까?

$\Rightarrow$라고 생각 했는데 그냥 맞아버렸다.

대략 생각해보면 $sa[i]=x,~sa[i+1]=y~~(0 \le i < n - 1)$ 라고 하자.

$y$의 suffix는 $x$의 suffix보다 사전순으로 뒤여야 한다.

그럼 $y$의 문자를 $1$ 줄여본다.

이것이 $x,y$의 접미사들의 사전순서를 유지한다면 그렇게 정답을 만들 수 있다.

이러한 $i$가 없다고 하자.

$y$의 문자를 $1$줄였을 때 $x$의 사전순보다 작아진다.

그럼 $x$ 도 $y$보다 다시 작아지기 위해 줄여야하는데, 그럼 $x$ 도 원래 $sa[i-1]$ 보다 $1$ 줄였을 때 작아지는 친구이므로 $x$를 $1$만 줄여도 $sa[i-1]$ 도 계속 줄여야한다.

이러한 과정이 유한히 반복되어 더 이상 무언갈 줄일 수 없는 상태가 되기 때문에 정답이 없다.