找到字符串的最长边框

Question

首先,让我告诉你字符串的边框是什么,

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

字符串的边框是一个子字符串,它既是正确的前缀又是字符串的正确后缀 - "正确"意味着整个字符串不算作子字符串.最长的边界x是"ab".最长的边界y是"abab"(前缀和后缀可以重叠).

另一个例子:
在字符串" abcde hgrab abcde "中,"abcde"是前缀和后缀.因此它也是上面字符串中最长的边界.

如何找到字符串最长的边框？

Answer 1

找到"字符串的边界"是Knuth-Morris-Pratt算法的前缀函数(也称为失效函数).用c ++实现(这个代码的一个改变版本):

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版本:http://ideone.com/hTW8FL

这种算法的复杂性是O(n).

Answer 2

如果您正在谈论字符数组，我认为您需要以下内容。这是基于边界是字符串的第一个和最后一个字符。你的例子并不清楚边界是什么。您需要更清楚地定义边界是什么。

x = abcde
border = { x[0], x[length(x)-1) }

如果你需要长度

length(z) {
    return sizeof(z) / (sizeof(z[0])