SRM630D1Med SuffixArrayDiv1
似たようなの解いたことある
問題概要(原文)
SuffixArrayが与えられる．このSuffixArrayを満たす文字列を構成するために文字の種類は最小いくつあれば足りるか？
考察
$SA_i$ 番目の文字と， $SA_{i+1}$ 番目の文字を同じに出来るかどうかを考える．$i$ 番目の文字を先頭とする suffix のランクを $\text{rank}(i)$ とおく．
$p=SA_i$, $a=SA_{i+1}$ とおく，また， $q=rank(p+1),b=rank(a+1)$ とする． $q < b$ のとき， $p$ 番目の文字と， $a$ 番目の文字は同じでもよく． $q > b$ のとき， $p$ 番目の文字と $a$ 番目の文字が同じではSAが壊れることが示される．
計算量は $O(N)$
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class SuffixArrayDiv1
{
public int minimalCharacters(int[] SA)
{
var ret = 1;
var n = SA.Length;
var ISA = new int[n + 1];
for (int i = 0; i < n; i++)
ISA[SA[i]] = i;
ISA[n] = -1;
for (int i = 1; i < n; i++)
{
var p = SA[i - 1];
var q = p + 1;
var r = ISA[q];
var a = SA[i];
var b = a + 1;
var c = ISA[b];
if (r < c) continue;
else ret++;
}
return ret;
}
}
コメント
- アメ文字のwriterなのでネ，これは解けるよね
