§ Prefix/Border function

Function that for a string s, at index i, returns the length of the longest border of s[0..i] (inclusive). For example, consider the string s=abababcaab.

• at i=0, we have substring s[0..0]=a which has no border (border is proper prefix/suffix). So pr(0) = 0.
• at i=1, we have substring s[0..1]=ab which has no border, so pr(1) = 0.
• at i=2, we have substring s[0..2]=aba which has a..a as border. pr(2) = 1
• at i=3, we have substring s[0..3]=abab which has ab..ab as border. pr(3) = 2
• at i=4, we have substring s[0..4]=ababa which has ab[a]ba as border (that is, the prefix is aba and the suffix is aba which overlaps). pr(4) = 3.
• at i=5, we have substring s[0..5]=ababab which has ab[ab]ab as border (that is, the prefix is abab and the suffix is abab which overlaps). pr(5) = 4.
• at i=6, we have substring s[0..6]=abababc which has no border. pr(6) = 0.
• at i=7, we have substring s[0..7]=abababca which has border a..a. pr(7) = 1.
• at i=8, we have substring s[0..8]=abababcab which has border ab..ab. pr(8) = 2.

In toto, the prefix function is:

  ababcaab
  01234012

§ s[0..i] has a border of length at pr(i+1)-1

• That is, given the substring s[0..i], we can predict that s[0..i] will have some border (perhaps not the longest border) of length pr(i+1)-1.
• Suppose s[0..i+1] has longest border of length L=pr(i+1) (by definition of pr). Suppose pr(i+1) >= 1. Then I can write s[0..i+1] as:

s[0..i+1] = p[0]p[1]...p[L]|s[L+1]...s[i+1-L-1]|p[0]p[1]...p[L]
            ^^^^^^^^^^^^^^^                     ^^^^^^^^^^^^^^^

If I now want to consider s[0..i], I need to drop the last letter p[L], which leaves me with:

s[0..i] = p[0]p[1]...p[L-1]p[L]|s[L+1]...s[i+1-L-1]|p[0]p[1]...p[L-1]
          ^^^^^^^^^^^^^^^^^                         ^^^^^^^^^^^^^^^^^

• where we have a border of p[0]...p[L-1].
• There maybe a longer border, involving other terms of s[0..i]. But we know that the border is at least pr(i) >= pr(i+1)-1.
• Upon re-arranging, we see that pr(i+1) <= pr(i) + 1.
• This tells us that the border can increase by at most 1 (it can drop to zero, no lower bound!). So we have: 0 <= pr(i+1) <= pr(i) + 1.
• So if we think of borders of s[0..i+1], we know that the longest border can be of length of border pr(i) + 1. All other borders will be of length <= pr(i), so these other borders will be borders of s[0..i]!
• Thus, to move from s[0..i] to s[0..(i+1)], we simply need to be able to find the longest border of s[0..(i+1)]. All other borders will come from s[0..i].

§ Lemma: Enumerating borders (what is a good name for this lemma?)

• Think of the longest border 123456:

123456----123456
     ^         ^
     L         N

• Now consider a shorter border ab:

ab3456----1234ab
     ^         ^
     L         N

• But we must have a~1 and b~2 since it's the same string! So the border is really ab34ab, and the string is:

ab34ab----ab34ab
     ^         ^
     L         N

• This shows that given the longest border 123456 of s[0:N] which has length L, any other border of s[0:N](such as ab) is also a border of s[0:L].
• Generalizing, given the longest border of s[0..n] of length L, any smaller border of s[0:N]is a border of s[0:L].

§ Algorithm to enumerate borders.

All borders of s[0:N] can be enumerated by:

1. Taking the longest border of length L of s[0:N] (given by pr(N)).
2. considering the border as being the substring s[0:L] (given by pr(L)).
3. Taking the longest border of s[0:L]
4. ... recurse till we hit empty string.

§ Computing pr(i+1)

1. We know that pr(0) = 0.
2. At pr(i+1), we know that s[0:pr(i)] = s[-pr(i):-1]

§ Border function is a fractal

Consider a general string which looks like:

abcdef--abcdef

If we think of the second longest border, say 12, we will get that the string must be:

12cdef--abcd12
     ^^  &&

But this implies that the occurrence of ef (marked with &&) and the occurrence of ab (marked with ##) must be 12, 12 respectively. This means that the string is:

12cd12--12cd12

So we started with a full string:

------------------

Then matched the left and right (very 1/3 cantor):

-------    ------
       ----

Then matched the left and right of these again and unified the leftovers, finding that it looks like:

--  --   --  --
  --       --
      ---

and so on. Isn't this so cool? Borders of a string are a fractal-like object!