最长的最大重复子串

Question

子字符串可以是长度为1、2、3...的一段字符。 我尝试解决的问题是找到出现次数最多的子字符串。因此，这基本上可以分解为查找具有最大频率的字符。 然而，我发现可以使用后缀树在O(n)时间内找到最长重复的子字符串。 但是，后缀树返回子字符串时优先考虑其长度。 我想要找到出现次数最多的子字符串，并从这些子字符串中找到最长的一个。 例如：

In the following string: ABCZLMNABCZLMNABC
A suffix tree will return ABCZLMN as the longest repeating substring.
However, what I am looking for is ABC;  as it is the longest out of all the ones having frequency = 3. 

我尝试通过生成位于两个索引i和j之间的子字符串来解决这个问题。然后，使用运行时间为O(n)的Z算法在每种情况下找到这些子字符串的出现次数。然而，总复杂度为O(n^3)。

我的O(n^3)代码

map<ll,vector<string>> m;
    string s; cin >> s;
    for(ll i=0;i<s.length();i++){
        string c;
        for(ll len=0; i+len<s.length();len++){
            c+=s[i+len];
            ll z[N];
            ll l=0,r=0;
            string kk;
            for(ll p=0;p<c.length();p++){
                kk+=c[p];
            }
            kk+="#";
            for(ll p=0;p<s.length();p++){
                kk+=s[p];
            }
            for(ll k=1;k<kk.length();k++){
                if(k>r){
                    l=r=k;
                    while(r<c.length()&&kk[r-l]==kk[r])r++;
                    z[k]=r-l;
                    r--;
                }
                else{
                    ll m=k-l;
                    if(z[m]<r-k+l)z[k]=z[m];
                    else{
                        l=k;
                        while(r<c.length()&&kk[r-l]==kk[r])r++;
                        z[k]=r-l;
                        r--;
                    }
                }
            }
            ll occ=0;
            for(ll n=0;n<kk.length();n++){
                if(z[n]==c.length())occ++;
            }
            m[occ].push_back(c);
        }
    }

我找不到适合的解决方案来提高效率。 请帮忙。 谢谢。

- Anand Zutshi

---

嘿... 作业吗？ Stack Overflow 不是“替我做”网站。试着写一些代码，如果出了问题再回来。 - folibis

好的，但请至少展示你的代码。 - folibis

我尝试通过生成两个索引i和j之间的子字符串来解决这个问题。然后，使用运行时间为O(n)的Z算法在每种情况下找到这些子字符串的出现次数。然而，总复杂度为O(n^3)。 - Anand Zutshi

一个单独的字符算不算子字符串？如果是，那么重复次数最多的子字符串必须重复与最常见字符相同的次数。正确吗？ - samgak

@samgak 是的，你说得对，这将会实现，但是我正在寻找所有字符串中最长的重复子串。请参考我在帖子中提供的示例。 - Anand Zutshi

好的，但要考虑这样做的影响：您只需要计算每个字符的频率，并找到具有相等最高频率的字符。其中一个必须是您最长重复子字符串的第一个字符。因此，只需测试每个字符即可。它的时间复杂度为O(n * k)，其中k是可能字符的数量。 - samgak

Answer 1

单个字符也算作子串，因此最大重复子串的频率必须等于该字符串中出现最多的字符的频率。其中一个含义是最大重复子串中的每个字符在该字符串中只能出现一次，因为如果它出现超过一次，那么该字符本身就会成为最大重复子串。例如，在字符串"dadxdadydadzdadydad"中，子串"dad"出现了5次，但子串"d"出现了10次。它们还必须以相同的顺序每次出现（否则单个字符的频率会比子串高，并且它们将成为最大重复子串本身）。它们也不能单独出现（否则它们将再次成为最大重复子串）。因此，最大重复子串必须由等量的最频繁出现的字符的子集（或全部）组成。我们可以通过对字符串进行一次遍历并计数来轻松确定这些字符是哪些。我们还可以通过跟踪每个字符之前和之后出现的字符并存储该字符来推断它们以哪种顺序出现，如果每次都相同，则为该字符；否则为零。例如，在字符串"abcxabcyabczabcyabc"中，字符"b"始终由字符"a"前缀和字符"c"后缀：

string s; cin >> s;
int i, freq[256];
char prev[256], next[256];
for(i = 1; i < 256; i++)
    freq[i] = prev[i] = next[i] = 0;
int maxFreq = 0;
for(i = 0; i < s.length(); i++)
{
    char c = s[i];
    char p = (i == 0) ? 0 : s[i-1];
    char n = (i < s.length() - 1) ? s[i+1] : 0;
    if(freq[c] == 0) // first time to encounter this character
    {
        prev[c] = p;
        next[c] = n;
    }
    else // check if it is always preceded and followed by the same characters:
    {
        if(prev[c] != p)
            prev[c] = 0;
        if(next[c] != n)
            next[c] = 0;
    }
    // increment frequency and track the maximum:
    if(++freq[c] > maxFreq)
        maxFreq = freq[c];
}

if(maxFreq == 0)
    return 0;

然后，我们可以遍历每个字符并找到频率等于最大频率的字符中，通过跟随next字符索引可以形成的字符串长度：

int maxLen = 0;
int startingChar = 0;
for(i = 1; i < 256; i++)
{
    // should have a frequency equal to the max and not be preceded
    // by the same character each time (or it is in the middle of the string)
    if((freq[i] == maxFreq) && (prev[i] == 0))
    {
        int len = 1, j = i;
        while(next[j] != 0)
        {
            len++;
            j = next[j];
        }
        if(len > maxLen)
        {
            maxLen = len;
            startingChar = i;
        }
    }
}

找到最大重复子串后，打印出来：

// print out the maximum length string:
int j = startingChar;
while(j != 0)
{
    cout << (char)j;
    j = next[j];
}
cout << endl;

如果您不喜欢遍历那些固定大小的数组或需要支持UNICODE字符等，您可以使用从字符类型到包含字符频率、上一个和下一个字符的结构体的 map。

- samgak