Border and Prefix of a String

Border of String

For string ‘abacabab’, the border is 'ab' as its present at both the start and end of the string.

Explanation

Adjusting the index to reuse identified border of the shorter string str[0..i- 1] when there is a mismatch is important.

For string abacabab i = 6, border/index = 3.

Now to find border at i = 7, since str[3] != str[7], we set index = border[3 - 1] = 1 and find str[1] == str[7]. So we increment index and 2 is the border.

 This works because,

aba is border when i = 6 (aba c aba)

a is border when i = 2 (a b a)

when we cannot expand on aba, we use the border of aba which is a, to expand the matching.


Code

using System;
using System.Linq;
namespace Border
{
    class Program
    {
        static void Main(string[] args)
        {
            String str = " abacabab";
            foreach (int n in getBorder(str))
                Console.WriteLine(n);
            Console.ReadKey();
        }
        private static int[] getBorder(string str)
        {
            int length = str.Length;
            int index = 0;
            int[] borderArr = new int[length];
            for (int i = 1; i < length; i++)
            {
                borderArr[i - 1] = index;
                while (index >= 0 && str.ElementAt(index) != str.ElementAt(i))
                {
                    if (index == 0)
                        index--;
                    else
                        index = borderArr[index - 1];
                }
                index++;
            }
            borderArr[length - 1] = index;
            return borderArr;
        }
    }
}


Prefix array of String

It’s the LCP of a string.

Explanation

Adjusting the index to reuse identified prefix of the shorter string str[0..i- 1] is important.

For string abbabaabbabaa i = 7, backindex = 6 index = 13.

Since the prefix for string starting at i = 6 extended till 13, the prefix for i=7 will be minimum of prefix of string starting at 7-6 --> which is 0, or 13 – 7 which is 6.

Code

using System;
using System.Linq;
 
namespace Prefix
{
   class Program
    {
        static void Main(string[] args)
        {
            String str = "abbabaabbabaaaabbabbaa";
            foreach (int n in getPrefix(str))
                Console.WriteLine(n);
            Console.ReadKey();
        }
 
        private static int[] getPrefix(string str)
        {
            int length = str.Length;
            int index = 0;
            int backindex = 0;
            int[] prefixArr = new int[length];
            prefixArr[0] = length;

            for (int i = 1; i < length; i++)
            {
                if (i < index && prefixArr[i - backindex] != index - i)
                    prefixArr[i] = Math.Min(prefixArr[i - backindex], index - i);
                else
                {
                    index = Math.Max(index, i);
                    backindex = i;
                    while (index < length && str.ElementAt(index) == str.ElementAt(index - backindex))
                        index++;
                    prefixArr[i] = index - backindex;
                }
            }
            return prefixArr;
        }
    }
}