如何从多组数组中查找跨数组重复的多元素序列？C#最优方案咨询

嘿，这个问题其实是序列模式挖掘里的经典场景——找多个数组间的公共连续子序列（长度≥2）。我在C#里处理过类似需求，给你两个最优方案，分场景选就行：

方案一：滚动哈希+全局哈希表（易实现，适合中小规模数据） #

这个思路简单直接，核心是把所有可能的长≥2的连续子序列转换成唯一标识，然后跟踪哪些标识出现在不同数组里。

具体步骤： #

• 给每个数组分配唯一ID，避免把同一个数组内的重复序列算进去
• 遍历每个数组的所有连续子序列（长度从2到数组本身长度）
• 把每个子序列转成字符串（比如"010,002,007"），用哈希表存起来：键是子序列字符串，值是出现过这个序列的数组ID集合
• 最后筛选出那些ID集合大小≥2的子序列，就是跨数组重复的序列

C#简化实现代码： #

using System;
using System.Collections.Generic;
using System.Linq;

public class CommonSequenceFinder
{
    public static Dictionary<string, HashSet<int>> FindCrossArraySequences(List<List<string>> inputArrays)
    {
        var sequenceTracker = new Dictionary<string, HashSet<int>>();

        // 遍历每个数组，给每个数组分配唯一ID
        for (int arrayIndex = 0; arrayIndex < inputArrays.Count; arrayIndex++)
        {
            var currentArray = inputArrays[arrayIndex];
            int arrayLength = currentArray.Count;

            // 遍历所有可能的子序列长度（从2开始）
            for (int subSeqLength = 2; subSeqLength <= arrayLength; subSeqLength++)
            {
                // 滑动窗口取所有该长度的子序列
                for (int startPos = 0; startPos <= arrayLength - subSeqLength; startPos++)
                {
                    var subSequence = string.Join(",", currentArray.Skip(startPos).Take(subSeqLength));
                    
                    if (!sequenceTracker.ContainsKey(subSequence))
                    {
                        sequenceTracker[subSequence] = new HashSet<int>();
                    }
                    // 把当前数组ID加入集合，自动去重
                    sequenceTracker[subSequence].Add(arrayIndex);
                }
            }
        }

        // 只保留在至少两个不同数组中出现的序列
        return sequenceTracker
            .Where(kv => kv.Value.Count >= 2)
            .ToDictionary(kv => kv.Key, kv => kv.Value);
    }

    public static void Main()
    {
        var testArrays = new List<List<string>>
        {
            new List<string> {"090","010","002","007","310","104","048","610","720"},
            new List<string> {"456","010","002","007","087","011","345","547","800"},
            new List<string> {"004","089","870","011","345","547","800","001","002"}
        };

        var result = FindCrossArraySequences(testArrays);
        foreach (var entry in result)
        {
            Console.WriteLine($"找到公共序列: {entry.Key}，出现在数组索引: {string.Join(", ", entry.Value)}");
        }
    }
}

优化小贴士： #

• 如果数据量很大，直接存字符串当键太占内存，可以换成双滚动哈希（用两个不同的基数和模值生成哈希对），既降低碰撞概率，又减少内存占用
• 预处理前缀哈希数组可以加速滚动哈希的计算，避免重复拼接字符串

方案二：后缀自动机（Suffix Automaton，高性能，适合大规模数据） #

如果你的数组数量多、长度长（比如单个数组上千元素，几十个数组），后缀自动机是最优解——它能线性时间压缩单个序列的所有子序列，然后通过多自动机求交集快速找到公共子序列。

核心逻辑： #

1. 为第一个数组构建后缀自动机，这个结构能高效表示所有可能的子序列
2. 用第二个数组去匹配这个自动机，记录所有匹配到的长度≥2的子序列，生成一个交集自动机
3. 再用第三个数组去匹配这个交集自动机，以此类推
4. 最终从自动机中提取出所有符合条件的公共子序列

这个方法时间复杂度是线性的，但实现门槛较高，需要对后缀自动机的结构有一定了解。如果你的数据规模没到那种程度，方案一完全够用。

选哪个？ #

• 中小规模数据（数组长度≤500，数量≤20）：选方案一，代码好写好调，够用
• 大规模数据：直接上后缀自动机，性能碾压暴力枚举和普通哈希方法

另外提一句：如果只需要找最长的公共连续子序列，两两数组比较可以用动态规划，但多数组场景还是上面两个方法更靠谱。

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