如何检测子列表是否连续存在于指定列表集合的任一列表内

我有一个主列表：

public List<List<string>> validOrders = new List<List<string>>
{
    new List<string> { "01", "02", "03", "04", "05", "06" },
    new List<string> { "02", "03", "01", "04", "05", "06" },
    new List<string> { "02", "03", "04", "01", "05", "06" },
};

还有一个子列表childObjectsPrefix，需要检查这个子列表是否作为连续序列出现在validOrders的任意一个列表中。

测试用例：

List<string> test1 = new List<string> { "01", "04" }; // False
List<string> test2 = new List<string> { "01", "02" }; // True
List<string> test3 = new List<string> { "02", "01" }; // False
List<string> test4 = new List<string> { "02", "03", "01" }; // True
List<string> test5 = new List<string> { "02", "03", "05" }; // False

我已经会检查子集，但连续序列的检测不知道怎么做，求解决方案。

解决方案 #

方法1：暴力匹配（直观易实现） #

遍历validOrders中的每个主列表，对每个主列表，检查是否存在起始索引，使得从该索引开始的连续元素完全匹配子列表。

public bool IsContinuousSubsequence(List<string> subList, List<List<string>> mainLists)
{
    // 子列表为空可直接返回true，若业务不允许空列表可添加判断
    if (subList.Count == 0)
        return true;
    
    foreach (var mainList in mainLists)
    {
        // 主列表长度小于子列表，直接跳过
        if (mainList.Count < subList.Count)
            continue;
        
        // 遍历所有可能的起始位置
        for (int i = 0; i <= mainList.Count - subList.Count; i++)
        {
            bool match = true;
            for (int j = 0; j < subList.Count; j++)
            {
                if (!mainList[i + j].Equals(subList[j]))
                {
                    match = false;
                    break;
                }
            }
            if (match)
                return true;
        }
    }
    return false;
}

调用示例：

var test1 = new List<string> { "01", "04" };
Console.WriteLine(IsContinuousSubsequence(test1, validOrders)); // 输出 False

var test4 = new List<string> { "02", "03", "01" };
Console.WriteLine(IsContinuousSubsequence(test4, validOrders)); // 输出 True

方法2：字符串拼接匹配（简洁但需注意元素特殊性） #

把列表元素用不会出现在元素中的分隔符拼接成字符串，然后检查子列表的拼接字符串是否是主列表拼接字符串的子串。

注意：如果元素可能包含所选分隔符（比如|），需要更换为不会冲突的分隔符，或者用特殊标记包裹元素。

public bool IsContinuousSubsequenceByString(List<string> subList, List<List<string>> mainLists)
{
    if (subList.Count == 0)
        return true;
    
    string subStr = string.Join("|", subList);
    
    foreach (var mainList in mainLists)
    {
        if (mainList.Count < subList.Count)
            continue;
        
        string mainStr = string.Join("|", mainList);
        if (mainStr.Contains(subStr))
            return true;
    }
    return false;
}

方法3：KMP算法（高效匹配，适合大列表） #

如果主列表和子列表数据量较大，暴力匹配效率不足，可以用KMP算法优化匹配过程，通过构建前缀函数减少重复比较。

// 构建前缀函数数组
private int[] BuildPrefixFunction(List<string> pattern)
{
    int[] prefix = new int[pattern.Count];
    int len = 0;
    int i = 1;
    
    while (i < pattern.Count)
    {
        if (pattern[i].Equals(pattern[len]))
        {
            len++;
            prefix[i] = len;
            i++;
        }
        else
        {
            if (len != 0)
                len = prefix[len - 1];
            else
            {
                prefix[i] = 0;
                i++;
            }
        }
    }
    return prefix;
}

// KMP核心匹配逻辑
public bool KMPMatch(List<string> text, List<string> pattern)
{
    if (pattern.Count == 0)
        return true;
    if (text.Count < pattern.Count)
        return false;
    
    int[] prefix = BuildPrefixFunction(pattern);
    int i = 0; // 主列表指针
    int j = 0; // 子列表指针
    
    while (i < text.Count)
    {
        if (text[i].Equals(pattern[j]))
        {
            i++;
            j++;
            if (j == pattern.Count)
                return true;
        }
        else
        {
            if (j != 0)
                j = prefix[j - 1];
            else
                i++;
        }
    }
    return false;
}

// 对外调用方法
public bool IsContinuousSubsequenceKMP(List<string> subList, List<List<string>> mainLists)
{
    foreach (var mainList in mainLists)
    {
        if (KMPMatch(mainList, subList))
            return true;
    }
    return false;
}

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