如何按顺序查找Array2的部分或全部元素在Array1中的首次出现索引

你需要实现的是在长数组Array1中，查找与短数组Array2的前缀完全匹配的连续子数组的最早起始索引，你给出的示例中Array2的前3个元素["in", "the", "barn"]正好对应Array1索引9开始的3个元素，因此期望返回9。

最高效的实现方案为适配数组场景的KMP（Knuth-Morris-Pratt）匹配算法，该算法时间复杂度为O(n+m)，其中n为Array1长度，m为Array2长度，避免了暴力匹配中重复回溯比对的性能损耗，在数组元素量级较大时优势尤其明显。

完整实现代码 #

using System;

public class ArrayPrefixMatch
{
    // 泛型方法，支持任意实现IEquatable<T>接口的元素类型数组匹配
    public static int FindFirstPrefixMatchIndex<T>(T[] textArray, T[] patternArray) where T : IEquatable<T>
    {
        // 边界校验
        if (textArray == null || patternArray == null || textArray.Length == 0 || patternArray.Length == 0)
            return -1;
        
        int textLen = textArray.Length;
        int patternLen = patternArray.Length;
        
        // 第一步：计算模式串的最长公共前后缀表（LPS数组，也叫部分匹配表）
        int[] lps = new int[patternLen];
        int maxPrefixLen = 0; // 当前最长公共前后缀的长度
        int index = 1;
        while (index < patternLen)
        {
            if (patternArray[index].Equals(patternArray[maxPrefixLen]))
            {
                maxPrefixLen++;
                lps[index] = maxPrefixLen;
                index++;
            }
            else
            {
                if (maxPrefixLen != 0)
                {
                    maxPrefixLen = lps[maxPrefixLen - 1];
                }
                else
                {
                    lps[index] = 0;
                    index++;
                }
            }
        }
        
        // 第二步：使用LPS数组执行KMP匹配，记录最长匹配对应的起始索引
        int textIndex = 0;
        int patternIndex = 0;
        int maxMatchLen = 0;
        int resultIndex = -1;
        
        while (textIndex < textLen)
        {
            if (patternArray[patternIndex].Equals(textArray[textIndex]))
            {
                textIndex++;
                patternIndex++;
                // 更新最长匹配记录
                if (patternIndex > maxMatchLen)
                {
                    maxMatchLen = patternIndex;
                    resultIndex = textIndex - patternIndex;
                    // 已完整匹配整个模式串，直接返回即可，不存在更长的匹配可能
                    if (maxMatchLen == patternLen)
                        return resultIndex;
                }
            }
            if (textIndex < textLen && !patternArray[patternIndex].Equals(textArray[textIndex]))
            {
                if (patternIndex != 0)
                    patternIndex = lps[patternIndex - 1];
                else
                    textIndex++;
            }
        }
        // 至少匹配1个元素才返回有效索引，否则返回-1
        return maxMatchLen >= 1 ? resultIndex : -1;
    }

    public static void Main()
    {
        string[] Array1 = { "the", "quick", "brown", "fox", "jumps",
                            "over", "the", "lazy", "dog", "in", "the",
                            "barn" };

        string[] Array2 = { "in", "the", "barn", "next", "to",
                            "the", "chickens" };
        
        int index = FindFirstPrefixMatchIndex(Array1, Array2);
        Console.WriteLine("The first occurrence of partial Array2 is at index {0}.", index);
        // 输出结果为9，符合预期
    }
}

小数组场景的简化实现 #

如果你处理的数组长度都非常小（单个数组元素数低于100），也可以用暴力匹配实现，代码更简洁，但最坏时间复杂度为O(n*m)，不适合大数组场景：

public static int BruteForcePrefixMatch<T>(T[] textArray, T[] patternArray) where T : IEquatable<T>
{
    if (textArray == null || patternArray == null || textArray.Length == 0 || patternArray.Length == 0)
        return -1;
    
    int maxMatchLen = 0;
    int resultIndex = -1;
    for (int i = 0; i < textArray.Length; i++)
    {
        int currentMatch = 0;
        for (int j = 0; j < patternArray.Length && i + j < textArray.Length; j++)
        {
            if (textArray[i + j].Equals(patternArray[j]))
                currentMatch++;
            else
                break;
        }
        if (currentMatch > maxMatchLen)
        {
            maxMatchLen = currentMatch;
            resultIndex = i;
            if (maxMatchLen == patternArray.Length)
                return resultIndex;
        }
    }
    return maxMatchLen > 0 ? resultIndex : -1;
}

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