関数 Ψ の性質 (3/5)
関数 Ψ は補題 7.2 の性質を満たす.
0≤i<j≤n に対し,T[SA[i]]=T[SA[j]] ならば Ψ[i]<Ψ[j].
定義より Ψ[i]=SA−1[SA[i]+1],Ψ[j]=SA−1[SA[j]+1] である.つまり,Ψ[i] と Ψ[j] の大小関係は接尾辞 T[SA[i]+1..n+1] と T[SA[i]+1..n+1] の辞書順で定義される.
今,T[SA[i]]=T[SA[j]] であるため,接尾辞 T[SA[i]+1..n+1] と T[SA[j]+1..n+1] の大小関係は T[SA[i]..n+1] と T[SA[j]..n+1] の大小関係と等しい. i<j であり,接尾辞配列の定義から T[SA[i]..n+1]<T[SA[j]..n+1] であるため,Ψ[i]<Ψ[j] となる.
気持ち
文字列 S,T について,S<T かつ S[1]=T[1] であるとき,S[2..]<T[2..] である.