如何优化最长前缀匹配算法？降低字符串匹配的时间复杂度

现有N个字符串（此处的"字符串"指抽象符号数组，不一定是文本字符串），需为每个字符串找出其之前的字符串中与它前缀最长匹配的字符串索引，无匹配则为-1。规则说明：

• "最长前缀匹配"指两个字符串的公共前缀长度最大
• 每个字符串仅与排在它前面的字符串比较
• 运算指基本操作，例如两两比较字符串会产生N*(N-1)/2次操作

示例：
输入集合：{ K, M, G, KG, MG, KMG, KGG, T, KT, MT, GT, KGT, MGT, MTT }
对应的输出：{ -1, -1, -1, 0, 1, 3, 5, -1, 6, 4, 2, 6, 4, 9 }

//AnyType[][] strings;
var result = new int[strings.Length];
for (var i = 1; i < strings.Length; i++)
{
    int matchIndex = -1, matchLength = 0;
    for (var j = i - 1; j >= 0; j--)
    {
        var length = Math.Min(strings[i].Length, strings[j].Length);
        var k = 0;
        for (; k < length && strings[i][k].Equals(strings[j][k]); k++) ;
        if (k <= matchLength)
            continue;
        matchLength = k;
        matchIndex = j;
    }
    result[i] = matchIndex;
}

原代码的时间复杂度约为O(N²*K)（K为平均匹配前缀长度），在N较大时效率极低，需要优化。

前缀树是专门处理前缀匹配的数据结构，可将时间复杂度降至O(N*K)（K为所有字符串的平均长度），大幅减少运算量。

实现思路 #

1. 前缀树节点设计：每个节点存储两个核心信息：
   • 子节点映射：键为字符串中的符号，值为对应的子节点
   • 最近索引：记录当前前缀对应的最后一个（最新的前置）字符串的索引
2. 逐个处理字符串：
   • 对第i个字符串，从根节点开始遍历其每个符号：每遍历一个符号，就记录当前节点的最近索引（作为当前前缀长度下的匹配候选），若符号无对应子节点则停止遍历
   • 遍历结束后，将最长匹配的索引存入结果数组
   • 最后将当前字符串插入前缀树，更新路径上所有节点的最近索引为i，确保后续字符串能匹配到最新的前置字符串

代码示例（抽象实现） #

// 定义前缀树节点
class TrieNode
{
    public Dictionary<AnyType, TrieNode> Children { get; } = new Dictionary<AnyType, TrieNode>();
    public int LastIndex { get; set; } = -1;
}

public int[] FindLongestPrefixMatch(AnyType[][] strings)
{
    int n = strings.Length;
    int[] result = new int[n];
    TrieNode root = new TrieNode();

    // 第一个字符串无前置匹配，结果为-1，插入前缀树
    result[0] = -1;
    TrieNode current = root;
    foreach (var symbol in strings[0])
    {
        if (!current.Children.ContainsKey(symbol))
        {
            current.Children[symbol] = new TrieNode();
        }
        current = current.Children[symbol];
        current.LastIndex = 0;
    }

    for (int i = 1; i < n; i++)
    {
        current = root;
        int maxLength = 0;
        int bestIndex = -1;
        AnyType[] currentStr = strings[i];

        for (int k = 0; k < currentStr.Length; k++)
        {
            var symbol = currentStr[k];
            if (current.Children.TryGetValue(symbol, out var child))
            {
                current = child;
                // 当前前缀长度为k+1，更新最优解
                if (k + 1 > maxLength)
                {
                    maxLength = k + 1;
                    bestIndex = current.LastIndex;
                }
            }
            else
            {
                break;
            }
        }
        result[i] = bestIndex;

        // 将当前字符串插入前缀树，更新路径上的LastIndex为i
        current = root;
        foreach (var symbol in currentStr)
        {
            if (!current.Children.ContainsKey(symbol))
            {
                current.Children[symbol] = new TrieNode();
            }
            current = current.Children[symbol];
            current.LastIndex = i;
        }
    }
    return result;
}

优化效果说明 #

• 每个字符串的查询和插入操作仅需遍历自身长度的符号，总操作次数为O(NK)，远低于原算法的O(N²K)
• 空间复杂度为O(N*K)，属于时间换空间的合理优化，在绝大多数场景下都可接受

内容的提问来源于stack exchange，提问作者Nickolas Etyuhibosecyu