如何在字符串数组中查找另一字符串数组的所有匹配起始索引

我们需要在主字符串数组中查找所有和目标子数组完全匹配的连续片段，返回所有匹配片段的起始索引。以你给出的示例为例：
主数组 a = {"a","b","c","d","e","f","g","c","d","e"}，子数组 b = {"d","e"}，最终匹配结果为 [3, 8]。 #

通用实现逻辑 #

• 先处理边界场景：如果子数组长度为0、或主数组长度小于子数组长度，直接返回空结果，不存在匹配可能。
• 遍历主数组的所有合法起始位置，起始位置最大取值为主数组长度 - 子数组长度，超出该值后剩余元素长度不足以匹配子数组。
• 对每个起始位置，依次对比后续连续元素是否和子数组每个位置元素完全相等：
  • 所有元素都匹配则将当前起始位置存入结果列表
  • 任意元素不匹配则直接终止当前对比，检查下一个起始位置

代码实现（C#） #

和你给出的示例语法风格对齐：

using System;
using System.Collections.Generic;

public class ArrayMatchHelper
{
    public static List<int> GetAllMatchStartIndices(string[] mainArray, string[] subArray)
    {
        List<int> matchIndices = new List<int>();
        int mainLen = mainArray.Length;
        int subLen = subArray.Length;
        
        // 边界判断
        if (subLen == 0 || mainLen < subLen)
            return matchIndices;
            
        for (int startIdx = 0; startIdx <= mainLen - subLen; startIdx++)
        {
            bool isFullMatch = true;
            for (int offset = 0; offset < subLen; offset++)
            {
                if (mainArray[startIdx + offset] != subArray[offset])
                {
                    isFullMatch = false;
                    break;
                }
            }
            if (isFullMatch)
            {
                matchIndices.Add(startIdx);
            }
        }
        return matchIndices;
    }

    // 测试代码
    public static void Main()
    {
        string[] a = {"a","b","c","d","e","f","g","c","d","e"};
        string[] b = {"d","e"};
        var result = GetAllMatchStartIndices(a, b);
        // 输出结果：3,8
        Console.WriteLine(string.Join(",", result));
    }
}

性能优化提示 #

如果处理的数组数据量很大，可以使用KMP算法优化匹配逻辑，将时间复杂度从O(n*m)（n为主数组长度、m为子数组长度）降低到O(n+m)，减少重复对比的开销。

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