Самая длинная максимальная повторяющаяся подстрока

Один символ считается подстрокой, поэтому максимальная повторяющаяся подстрока должна встречаться с частотой, равной частоте наиболее часто встречающегося символа в строке.

Одним из следствий этого является то, что каждый символ в максимально повторяющейся подстроке может встречаться в строке только один раз, потому что, если он встречается более одного раза, то этот символ сам по себе станет максимально повторяющейся строкой. Например, подстрока «папа» встречается в строке «dadxdadydadzdadydad» 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 из типа символа в структуру, содержащую частоту символов, а также предыдущие и следующие символы.