c# - 如何在两个字符串中找到共同的后缀？

Question

我正在尝试实现一些在多个字符串之间找到公共(public)后缀的东西，为了便于说明，请考虑以下内容:

"The quick brown fox""The not so quick brown fox""The smelly brown fox""The vicious brown fox"

To a human, it's hopefully obvious that the common suffix here is " brown fox", and my naive implementation currently takes the first pair of strings, converts them both to char arrays, and then iterates over these until a character is found to be different, I then create a new string from this, and crop it to the length, reverse it back to the correct order, and return that. I then repeat using the result from the first string with the next string in the list.

Whilst this is loosely O(N), performance of this isn't as good as I'd like, and I wondered before I spend a long time buried in the profiler if I'd missed a quicker way to do this within the .NET framework?

EDIT:Taking out the double reverses (which then means we don't need to convert to char arrays) gives pretty good performance, for the record, my implementation looks a little like:

    private string GetCommonSuffix(string[] lines)
    {
        int lineCount = lines.GetLength(0);

        string currentSuffix = lines[0];
        int currentSuffixLength = currentSuffix.Length;
        for (int i = 1; i < lineCount; i++)
        {
            string thisLine = lines[i];
            if (!thisLine.EndsWith(currentSuffix))
            {
                int thisLineLength = thisLine.Length;
                int maxPossible = thisLineLength < currentSuffixLength ? thisLineLength : currentSuffixLength;

                if (maxPossible == 0)
                {
                    return string.Empty;
                }

                for (int j = 1; j < maxPossible; j++)
                {
                    if( currentSuffix[ currentSuffixLength - j ] != thisLine[ thisLineLength - j ] )
                    {
                        currentSuffix = currentSuffix.Substring(currentSuffixLength - j + 1, j - 1);
                        currentSuffixLength = j - 1;
                        break;
                    }
                }
            }
        }

        return currentSuffix;
    }

Answer 1

好吧，首先您不需要将字符串转换为 char 数组。您可以在字符串中使用索引器来获取单个字符。

可能值得将其视为一个数字而不是一个字符串...每次成对比较都会给你一个最大值，而最终的数字(后缀的大小)是最小值这些最大值。

因此有两种方法:

• 从 0(始终有效)开始并逐步向上:检查 1 是否有效(即所有字符串以相同字符结尾)然后移动到 2(通过检查倒数第二个字符)等
• 从无穷大开始，然后进行成对比较以减少最大长度。当然，您不需要进行所有成对比较 - 只需将每个字符串与第一个字符串进行比较就可以了。

不过，就我个人而言，我可能会选择第一种方法——它不会有很好的缓存一致性，但我认为在某些情况下它会更好(例如，许多字符串，除了其中一个之外，所有的字符串都有一个长的共同点后缀。

(当然，一旦你得到了长度，得到实际的子串就很简单了。)