Border Array on Bounded Alphabet
|
Input:
f, an integer array
Σ, a bounded size alphabet
Σ, an unbounded size alphabet
Output:
a message telling wether f is a border array or not
an error message if Σ is not large enough
a word such that f is its border array (if f is valid)
|
→
T
r
y
i
t
→
|
|
if f[1]≠0 then
return "This array is not valid at index 1"
k[1]←1
word[1]←Σ[1]
for i←2 to n do
if f[i]=0 then
k[i]←1+k[f[i-1]+1]
if k[i]>|Σ| then
return "Alphabet size exceeded at index i"
word[i]←Σ[k[i]]
else
j←f[i-1]
while j+1>f[i] and f[j+1]≠f[i] do
j←f[j]
if j+1≠f[i] then
return "This array is not valid at index i"
k[i]←k[f[i-1]+1]
word[i]←word[f[i]]
return "This array is a border array"
References
J.-P. Duval, T. Lecroq and A. Lefebvre
Efficient validation and construction of border arrays and validation of string matching automata
RAIRO - Theoretical Informatics and Applications
43(2), 281-297, 2009
J.-P. Duval, T. Lecroq and A. Lefebvre
Border array on bounded alphabet
Journal of automata, languages and combinatorics
10(1), 51-60, 2005
