c++ - 在C++中，有没有找到在字符串中重复模式的子字符串的最佳方法？

Question

我正在为我的在线类(class)解决一个需要解决的问题。通常，我的老师会很乐意提供帮助，但现在无法联系他。问题如下:

如果彼此相邻有两个相同的子字符串，我们可以将其写为(substring)对其进行压缩。因此，我们可以将zz记为(z)，将zzzz记为((z))或zzzzzzzzzzbbbb记为(((z)))(z)(b)。给定一个压缩的文本，检查压缩是否正确完成(如果可能)-解压缩并检查压缩是否以最佳方式完成，可能是通过再次最佳压缩来实现。

我已经编写了一个函数来检查压缩是否正确完成，解压缩功能和最佳压缩，但仅适用于仅使用一种模式(例如gorgorgorgorgorgor或zzzzzz)的字符串以及何时知道该模式。

std::string ifreapeats(std::string tes, std::string dotes){

int iloraz = dotes.length() / tes.length();
int pot2 = highestpow2(iloraz);
int roznica = iloraz - pot2;

std::string finale;

finale = "";

int logar = int(log(iloraz) / log(2));

    for(int i = 0; i < logar; ++i)
    {
        finale += '(';
    }

    finale += tes;

    for (int i = 0; i < logar; ++i)
    {
        finale += ')';
    }

    if (roznica == 1)
        return finale + tes;

    if (roznica == 0)
        return finale;

    std::string dotes2 = "";

    for (int i = 0; i < roznica; ++i)
    {
        dotes2 += tes;
    }

    finale += ifreapeats(tes, dotes2);

    return finale;}

其中highestpow2返回的小数幂小于或等于给定数字2。现在，我不知道如何将其应用于更复杂的字符串，这些字符串中有多个模式，并且序列中没有模式。例如aabbbaabbbxyzyz。它应该返回((a)(b)b)x(yz)。我猜找到最长的带图案的子字符串可能有用，但是我不知道如何应用它。同样，这比我们之前在IT类里面所做的事情更难解决问题。如果这不是问题，我希望得到一些解释，以便为类的其他学生提供帮助(每个人都希望我能设法解决问题，并帮助他们)。

对不起，我可能会犯一些语法错误。我也可能为波兰语留下了一些变量名称，对此我也表示歉意。

Answer 1

我还没有证明这种方法可以产生最佳的“压缩”效果，但是我的直觉是从最长的重复开始并向内进行。如果这不是最佳选择，那么我认为该任务已经超出了高中阶段的任务。

这个想法是:搜索最长的重复。找到它之后，该字符串可以分为ABBC部分，其中B是重复，而A和C是重复前后的子字符串。通过将A，'('，B，')的压缩和C的压缩级联来给出结果。如果未找到重复，则压缩为输入字符串。

您可以使用以下以伪代码编写的算法:

// size(S) is the size of the string
// substr(S, Pos, L) is substring of S with length L starting from Pos
// substr(S, Pos) is substring of S starting from Pos until the end of S
// S is the input string
compress(S)
    if size(S) < 2
        return S     // strings shorter than 2 cannot have repetition
    L = size(S) / 2  // L is initially longest possible repetition
    while L > 0
        for I = 0 ... size(S) - 2*L
            Left  = substr(S, I    , L)
            Right = substr(S, I + L, L)
            if Left == Right    // repetition found
                Beforeleft = substr(S, 0      , I)
                AfterRight = substr(S, I + 2*L)
                return
                    compress(Beforeleft) +
                    '(' +
                    compress(Left) +
                    ')' +
                    compress(AfterRight)
        L--     // no repetition of this length found; search for shorter
    return S    // no repetition of any length was found