DOTD: Table of Borders

1 Jul 2016

The border of a string x is defined as a substring u which is both a prefix and suffix of x = uvu, where v is an infix of x. For example, the longest border of the string ababbaabbaaba is aba.

 

The table of borders B(x), of length m = |x|, stores at each position B(x)[i], the length of the longest border of the substring x[0...i]. The table of borders for the example string above would be:

 

i              0    1    2   3   4   5   6   7   8  9  10  11  12
x[i]          a    b   a   b   b   a   a   b   b   a   a   b   a
B(x)[i]      0   0   1    2   0   1    1   2   0   1   1    2   3

 

Here is the algorithm BORDERS(x,m) to compute the table of borders B(x) given a string x and its length m as input. [1]

 

BORDERS(x,m)
1  i ← 0
2  for j ← 1 to m - 1 do
3            B[j - 1] ← i
4            while i ≤ 0 and x[j] ≠ x[i] do
5                      if i  = 0 then
6                                i ← -1
7                      else i ← B[i-1]
8            i ← i + 1
9  B[m-1] ← i
10 return B

 

[1] Crochemore, M., Hancart, C., & Lecroq, T. (2007). Algorithms on strings. Cambridge University Press.

Share on Facebook
Share on Twitter
Share on LinkedIn
Please reload

Please reload

Related Posts
PhDomics by Fatima