SRM 630 Div1 Med, SuffixArrayDiv1

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13377&rd=16061
ある文字列に対する接尾辞配列 SA が与えられている. 元の文字列は何種類のアルファベットで構成されているか. 最も少ない場合の種類数を求めよ.
接尾辞配列 - Wikipedia

文字列長は 1 以上 50 以下とする.

解法

接尾辞を辞書順に並べた時に, 先頭文字が最低何回変わらなければならないかを考える.
文字列の i 文字目を c(i), i 文字目以降の接尾辞を suff(i) で表すと,

suff(i) < suff(j) c(i) = c(j) かつ suff(i+1) < suff(j+1), または c(i) < c(j)

が成り立つ. これを用いて, 各 i について suff( SA[i] ) と suff( SA[i+1] ) の先頭文字を等しく出来るかどうかを確かめる.

解答

#include <iostream>
#include <vector>
#include <algorithm>
 
#define loop(n, i) for(int i=0;i<n;i++)
#define from_to(from, to, i) for(int i=from;i<=to;i++)

using namespace std;

class SuffixArrayDiv1
{
public:
    int minimalCharacters (vector <int> SA)
    {
        int N = SA.size();
        vector<int> I(N+1);
        loop (N, i) I[SA[i]] = i;
        I[N] = -1;

        int cnt = 0;
        loop (N-1, i) {
            if (I[SA[i]+1] > I[SA[i+1]+1]) cnt++;
        }

        return cnt+1;
    }
};