Finding the longest border of a string

Question

First, let me tell you what the border of a string is,

let x = "abacab"
let y = "ababab"

The border of a string is a substring which is both a proper prefix and proper suffix of the string — "proper" meaning that the whole string does not count as a substring. The longest border of x is "ab". The longest border of y is "abab" (the prefix and suffix can overlap).

Another example:
In string "abcde hgrab abcde", then "abcde" is a prefix as well as suffix. Thus it is also the longest border of the string above.

How can I find the longest border of a string?

Answer 1

Finding the "border of a string" is what the prefix function (also known as failure function) of Knuth-Morris-Pratt algorithm do. Implementation in c++ (a bit changed version of this code):

int longestBorder(const string& s) {
    int len = s.length();
    vector<int> prefixFunc(len); 
    prefixFunc[0] = 0;

    int curBorderLen = 0;   
    for (int i = 1; i < len; ++i) { 
        while (curBorderLen > 0 && s[curBorderLen] != s[i]) 
            curBorderLen = prefixFunc[curBorderLen - 1]; 

        if (s[curBorderLen] == s[i]) 
            ++curBorderLen;

        prefixFunc[i] = curBorderLen;
    }

    return prefixFunc[len-1];
}

Runnable version: http://ideone.com/hTW8FL

The complexity of this algorithm is O(n).