关于几种字符串查找算法的对比分析

发表于 2021-09-02 更新于 2022-06-08 分类于偶有所得本文字数： 4.5k 阅读时长 ≈ 16 分钟

昨日在新生命团队钉钉群中，看到大石头老师分享了他们实现的 IndexOf 算法，据说可以做到 O(1)，第一反应是几乎不可能，了解之后得知是使用了 Boyer Moore 字符串搜索算法，据说这种算法常用于 IDE 工具的查找，比 KMP 更快，所以有了对各种常用字符串查找算法做一下 Benchmark 的想法。

横向对比的各个字符串查找算法

string.IndexOf

此方法为 FLC 中实现的 string 类型的方法，以下源码均已开源在 GitHub 。

// Determines the position within this string of the first occurence of the specified
// string, according to the specified search criteria.  The search begins at
// the first character of this string, it is case-sensitive and ordinal (code-point)
// comparison is used.
//
[Pure]
public int IndexOf(String value) {
    return IndexOf(value, StringComparison.CurrentCulture);
}

可以看到，默认使用了 StringComprison.CurrentCulture，关于其具体的定义，可以参照官方文档：

通常情况我们使用 CurrentCulture 或是 Ordinal 都能很好的满足需求。

继续向下看（源码为节选，省略了无关内容）

[Pure]
public int IndexOf(String value, StringComparison comparisonType) {
    return IndexOf(value, 0, this.Length, comparisonType);
}
[Pure]
[System.Security.SecuritySafeCritical]
public int IndexOf(String value, int startIndex, int count, StringComparison comparisonType) {
    // Validate inputs
    if (value == null)
        throw new ArgumentNullException("value");

    if (startIndex < 0 || startIndex > this.Length)
        throw new ArgumentOutOfRangeException("startIndex", Environment.GetResourceString("ArgumentOutOfRange_Index"));

    if (count < 0 || startIndex > this.Length - count)
        throw new ArgumentOutOfRangeException("count", Environment.GetResourceString("ArgumentOutOfRange_Count"));
    Contract.EndContractBlock();

    switch (comparisonType) {
        case StringComparison.CurrentCulture:
            return CultureInfo.CurrentCulture.CompareInfo.IndexOf(this, value, startIndex, count, CompareOptions.None);

        case StringComparison.CurrentCultureIgnoreCase:
            return CultureInfo.CurrentCulture.CompareInfo.IndexOf(this, value, startIndex, count, CompareOptions.IgnoreCase);

        case StringComparison.InvariantCulture:
            return CultureInfo.InvariantCulture.CompareInfo.IndexOf(this, value, startIndex, count, CompareOptions.None);

        case StringComparison.InvariantCultureIgnoreCase:
            return CultureInfo.InvariantCulture.CompareInfo.IndexOf(this, value, startIndex, count, CompareOptions.IgnoreCase);

        case StringComparison.Ordinal:
            return CultureInfo.InvariantCulture.CompareInfo.IndexOf(this, value, startIndex, count, CompareOptions.Ordinal);

        case StringComparison.OrdinalIgnoreCase:
            if (value.IsAscii() && this.IsAscii())
                return CultureInfo.InvariantCulture.CompareInfo.IndexOf(this, value, startIndex, count, CompareOptions.IgnoreCase);
            else
                return TextInfo.IndexOfStringOrdinalIgnoreCase(this, value, startIndex, count);

        default:
            throw new ArgumentException(Environment.GetResourceString("NotSupported_StringComparison"), "comparisonType");
    }  
}

下面继续跟着源码来到 CompareInfo

public unsafe virtual int IndexOf(String source, char value, CompareOptions options)
{
    if (source==null)
        throw new ArgumentNullException("source");
    Contract.EndContractBlock();

    return IndexOf(source, value, 0, source.Length, options);
}

[System.Security.SecuritySafeCritical]  // auto-generated
[ResourceExposure(ResourceScope.None)]
[ResourceConsumption(ResourceScope.Process, ResourceScope.Process)]
public unsafe virtual int IndexOf(String source, char value, int startIndex, int count, CompareOptions options)
{
    // Validate inputs
    if (source == null)
        throw new ArgumentNullException("source");

    if (startIndex < 0 || startIndex > source.Length)
        throw new ArgumentOutOfRangeException("startIndex", Environment.GetResourceString("ArgumentOutOfRange_Index"));

    if (count < 0 || startIndex > source.Length - count)
        throw new ArgumentOutOfRangeException("count", Environment.GetResourceString("ArgumentOutOfRange_Count"));
    Contract.EndContractBlock();

    if (options == CompareOptions.OrdinalIgnoreCase)
    {
        // 
        return source.IndexOf(value.ToString(), startIndex, count, StringComparison.OrdinalIgnoreCase);
    }

    // Validate CompareOptions
    // Ordinal can't be selected with other flags
    if ((options & ValidIndexMaskOffFlags) != 0 && (options != CompareOptions.Ordinal))
        throw new ArgumentException(Environment.GetResourceString("Argument_InvalidFlag"), "options");

    // to let the sorting DLL do the call optimization in case of Ascii strings, we check if the strings are in Ascii and then send the flag RESERVED_FIND_ASCII_STRING  to 
    // the sorting DLL API SortFindString so sorting DLL don't have to check if the string is Ascii with every call to SortFindString.
    return InternalFindNLSStringEx(
                m_dataHandle, m_handleOrigin, m_sortName, 
                GetNativeCompareFlags(options) | Win32Native.FIND_FROMSTART | ((source.IsAscii() && (value <= '\x007f')) ? RESERVED_FIND_ASCII_STRING : 0),
                source, count, startIndex, new String(value, 1), 1);
}

 // InternalFindNLSStringEx parameters is not exactly matching kernel32::FindNLSStringEx parameters.
// Call through to NewApis::FindNLSStringEx so we can get the right behavior
[System.Security.SecurityCritical]  // auto-generated
[ResourceExposure(ResourceScope.None)]
[DllImport(JitHelpers.QCall, CharSet = CharSet.Unicode)]
[SuppressUnmanagedCodeSecurity]
private static extern int InternalFindNLSStringEx(IntPtr handle, IntPtr handleOrigin, String localeName, int flags, String source, int sourceCount, int startIndex, string target, int targetCount);

可以看到，最终是调用了 InternalFindNLSStringEx。

不同的选项被转换成了不同的 flag

[Pure]
internal static int GetNativeCompareFlags(CompareOptions options)
{
    // some NLS VM functions can handle COMPARE_OPTIONS_ORDINAL
    // in which case options should be simply cast to int instead of using this function
    // Does not look like the best approach to me but for now I am going to leave it as it is
    // 
    Contract.Assert(options != CompareOptions.OrdinalIgnoreCase, "[CompareInfo.GetNativeCompareFlags]CompareOptions.OrdinalIgnoreCase should be handled separately");

    // Use "linguistic casing" by default (load the culture's casing exception tables)
    int nativeCompareFlags = NORM_LINGUISTIC_CASING;

    if ((options & CompareOptions.IgnoreCase)       != 0) { nativeCompareFlags |= NORM_IGNORECASE;        }
    if ((options & CompareOptions.IgnoreKanaType)   != 0) { nativeCompareFlags |= NORM_IGNOREKANATYPE;    }
    if ((options & CompareOptions.IgnoreNonSpace)   != 0) { nativeCompareFlags |= NORM_IGNORENONSPACE;    }
    if ((options & CompareOptions.IgnoreSymbols)    != 0) { nativeCompareFlags |= NORM_IGNORESYMBOLS;     }
    if ((options & CompareOptions.IgnoreWidth)      != 0) { nativeCompareFlags |= NORM_IGNOREWIDTH;       }
    if ((options & CompareOptions.StringSort)       != 0) { nativeCompareFlags |= SORT_STRINGSORT;        }

    // Suffix & Prefix shouldn't use this, make sure to turn off the NORM_LINGUISTIC_CASING flag
    if (options == CompareOptions.Ordinal)                { nativeCompareFlags = COMPARE_OPTIONS_ORDINAL; }

    Contract.Assert(((options & ~(CompareOptions.IgnoreCase |
                                  CompareOptions.IgnoreKanaType |
                                  CompareOptions.IgnoreNonSpace |
                                  CompareOptions.IgnoreSymbols |
                                  CompareOptions.IgnoreWidth |
                                  CompareOptions.StringSort)) == 0) ||
                     (options == CompareOptions.Ordinal), "[CompareInfo.GetNativeCompareFlags]Expected all flags to be handled");

    Contract.Assert((nativeCompareFlags & RESERVED_FIND_ASCII_STRING) == 0, "[CompareInfo.GetNativeCompareFlags] RESERVED_FIND_ASCII_STRING shouldn't be set here");

    return nativeCompareFlags;
}

可以看到继续前进涉及到了 CLR 层的 comnlsinfo

//
//  Search for the character in the string.
//
Buffer1 = pString1->GetBuffer();
Buffer2 = pString2->GetBuffer();

if (dwFlags == COMPARE_OPTIONS_ORDINAL)
{
    iRetVal = FastIndexOfString(Buffer1, StartIndex, EndIndex, Buffer2, StringLength2);
    goto lExit;
}

其中 COMPARE_OPTIONS_ORDINAL 涉及到的是 FastIndexOfString


INT32 COMNlsInfo::FastIndexOfString(__in WCHAR *source, INT32 startIndex, INT32 endIndex, __in_ecount(patternLength) WCHAR *pattern, INT32 patternLength)
{
    CONTRACTL {
        NOTHROW;
        GC_NOTRIGGER;
        MODE_COOPERATIVE;
        SO_TOLERANT;
        PRECONDITION(CheckPointer(source));
        PRECONDITION(CheckPointer(pattern));
        PRECONDITION(startIndex >= 0);
        PRECONDITION(endIndex >= 0);
        PRECONDITION(patternLength>= 0);
    } CONTRACTL_END

    int endPattern = endIndex - patternLength + 1;

    if (endPattern<0) {
        return -1;
    }

    if (patternLength <= 0) {
        return startIndex;
    }

    WCHAR patternChar0 = pattern[0];
    for (int ctrSrc = startIndex; ctrSrc<=endPattern; ctrSrc++) {
        if (source[ctrSrc] != patternChar0)
            continue;
        int ctrPat;
        for (ctrPat = 1; (ctrPat < patternLength) && (source[ctrSrc + ctrPat] == pattern[ctrPat]); ctrPat++) {
            ;
        }
        if (ctrPat == patternLength) {
            return (ctrSrc);
        }
    }

    return (-1);
}

其余的则是 IndexOfString

FCIMPL7(INT32, COMNlsInfo::IndexOfString,
                    INT_PTR pNativeCompareInfo,
                    INT32 LCID,
                    StringObject* pString1UNSAFE,   // String to search in
                    StringObject* pString2UNSAFE,   // String we're looking for
                    INT32 StartIndex,               // Index to start at in search string
                    INT32 Count,                    // # of chars to search
                    INT32 dwFlags)
{
    CONTRACTL
    {
        THROWS;
        DISABLED(GC_TRIGGERS);
        MODE_ANY;
        SO_TOLERANT;
        PRECONDITION(CheckPointer((LPVOID)pNativeCompareInfo));
        PRECONDITION(CheckPointer(pString1UNSAFE));
        PRECONDITION(CheckPointer(pString2UNSAFE));
    } CONTRACTL_END;

    INT32       iRetVal = -1;
    STRINGREF   pString1 = (STRINGREF) pString1UNSAFE;
    STRINGREF   pString2 = (STRINGREF) pString2UNSAFE;

    HELPER_METHOD_FRAME_BEGIN_RET_2(pString1, pString2);

    WCHAR *Buffer1 = NULL;
    WCHAR *Buffer2 = NULL;

    //
    //  Get the arguments.
    //
    int StringLength1;
    int StringLength2;
    StringLength1 = pString1->GetStringLength();
    StringLength2 = pString2->GetStringLength();

    //
    //  Get the arguments.
    //
    _ASSERTE(StartIndex >= 0 && StartIndex <= StringLength1);

    int EndIndex = StartIndex - 1 + Count;

    _ASSERTE(Count >= 0 && EndIndex < StringLength1);

    //
    //  Check the ranges.
    //
    if (StringLength1 == 0)
    {
        if (StringLength2 == 0)
            iRetVal = 0;
        // else iRetVal = -1 (not found)
        goto lExit;
    }

    //
    //  See if we have an empty string 2.
    //
    if (StringLength2 == 0)
    {
        iRetVal = StartIndex;
        goto lExit;
    }

    //
    //  Search for the character in the string.
    //
    Buffer1 = pString1->GetBuffer();
    Buffer2 = pString2->GetBuffer();

    if (dwFlags == COMPARE_OPTIONS_ORDINAL)
    {
        iRetVal = FastIndexOfString(Buffer1, StartIndex, EndIndex, Buffer2, StringLength2);
        goto lExit;
    }

    //For dwFlags, 0 is the default, 1 is ignore case, we can handle both.
    if (dwFlags<=1 && IS_FAST_COMPARE_LOCALE(LCID))
    {
        //If we've never before looked at whether this string has high chars, do so now.
        if (IS_STRING_STATE_UNDETERMINED(pString1->GetHighCharState()))
        {
            COMString::InternalCheckHighChars(pString1);
        }

        //If we've never before looked at whether this string has high chars, do so now.
        if (IS_STRING_STATE_UNDETERMINED(pString2->GetHighCharState()))
        {
            COMString::InternalCheckHighChars(pString2);
        }

        //If neither string has high chars, we can use a much faster comparison algorithm.
        if (IS_FAST_INDEX(pString1->GetHighCharState()) && IS_FAST_INDEX(pString2->GetHighCharState()))
        {
            if (dwFlags==0)
                iRetVal = FastIndexOfString(Buffer1, StartIndex, EndIndex, Buffer2, StringLength2);
            else
                iRetVal = FastIndexOfStringInsensitive(Buffer1, StartIndex, EndIndex, Buffer2, StringLength2);
            goto lExit;
        }
    }

    iRetVal = ((NativeCompareInfo*)(pNativeCompareInfo))->IndexOfString(
        Buffer1, Buffer2, StartIndex, EndIndex, StringLength2, dwFlags, FALSE);

    // We checked flags in managed code, so this shouldn't happen.
    _ASSERTE(iRetVal != INDEXOF_INVALID_FLAGS);
//    if (iRetVal == INDEXOF_INVALID_FLAGS) {
//        COMPlusThrowArgumentException(L"flags", L"Argument_InvalidFlag");
//    }

lExit: ;
    HELPER_METHOD_FRAME_END();
    return iRetVal;

}
FCIMPLEND

FCIMPL5(INT32, COMNlsInfo::IndexOfStringOrdinalIgnoreCase,
                    INT_PTR     ptr,
                    StringObject* pString1UNSAFE,   // String to search in
                    StringObject* pString2UNSAFE,   // String we're looking for
                    INT32 StartIndex,               // Index to start at in search string
                    INT32 Count)                    // # of chars to search
{
    CONTRACTL
    {
        THROWS;
        DISABLED(GC_TRIGGERS);
        MODE_ANY;
        SO_TOLERANT;
        PRECONDITION(ptr != NULL);
        PRECONDITION(CheckPointer(pString1UNSAFE));
        PRECONDITION(CheckPointer(pString2UNSAFE));
    } CONTRACTL_END;

    INT32       iRetVal = -1;
    STRINGREF   pString1 = (STRINGREF) pString1UNSAFE;
    STRINGREF   pString2 = (STRINGREF) pString2UNSAFE;

    HELPER_METHOD_FRAME_BEGIN_RET_2(pString1, pString2);

    WCHAR *Buffer1 = NULL;
    WCHAR *Buffer2 = NULL;

    //
    //  Get the arguments.
    //
    int StringLength1;
    int StringLength2;
    StringLength1 = pString1->GetStringLength();
    StringLength2 = pString2->GetStringLength();

    //
    //  Get the arguments.
    //
    _ASSERTE(StartIndex >= 0 && StartIndex <= StringLength1);

    int EndIndex = StartIndex - 1 + Count;

    _ASSERTE(Count >= 0 && EndIndex < StringLength1);

    //
    //  Check the ranges.
    //
    if (StringLength1 == 0)
    {
        if (StringLength2 == 0)
            iRetVal = 0;
        // else iRetVal = -1 (not found)
        goto lExit;
    }

    //
    //  See if we have an empty string 2.
    //
    if (StringLength2 == 0)
    {
        iRetVal = StartIndex;
        goto lExit;
    }

    //
    //  Search for the character in the string.
    //
    Buffer1 = pString1->GetBuffer();
    Buffer2 = pString2->GetBuffer();

    //If we've never before looked at whether this string has high chars, do so now.
    if (IS_STRING_STATE_UNDETERMINED(pString1->GetHighCharState()))
    {
        COMString::InternalCheckHighChars(pString1);
    }
    
    //If we've never before looked at whether this string has high chars, do so now.
    if (IS_STRING_STATE_UNDETERMINED(pString2->GetHighCharState()))
    {
        COMString::InternalCheckHighChars(pString2);
    }
    
    //If neither string has high chars, we can use a much faster comparison algorithm.
    if (IS_FAST_INDEX(pString1->GetHighCharState()) && IS_FAST_INDEX(pString2->GetHighCharState())) {
        iRetVal = FastIndexOfStringInsensitive(Buffer1, StartIndex, EndIndex, Buffer2, StringLength2);
    }
    else {
        NativeTextInfo* pNativeTextInfo = (NativeTextInfo*)ptr;
        iRetVal = pNativeTextInfo->IndexOfStringOrdinalIgnoreCase(Buffer1, StartIndex, EndIndex, Buffer2, StringLength2);
    }

lExit: ;
    HELPER_METHOD_FRAME_END();
    return iRetVal;

}

`Span<Char>.IndexOf`

System.Span<T> 是在 .NET 中发挥关键作用的新值类型。使用它，可以表示任意内存的相邻区域，无论相应内存是与托管对象相关联，还是通过互操作由本机代码提供，亦或是位于堆栈上。除了具有上述用途外，它仍能确保安全访问和高性能特性，就像数组一样。
官方在 System.Memory.dll 中提供了 MemoryExtensions.IndexOf 方法，同样可以用于字符串的查找。

简单看一下源码
MemoryExtensions.Globalization.cs

/// <summary>
/// Reports the zero-based index of the first occurrence of the specified <paramref name="value"/> in the current <paramref name="span"/>.
/// <param name="span">The source span.</param>
/// <param name="value">The value to seek within the source span.</param>
/// <param name="comparisonType">One of the enumeration values that determines how the <paramref name="span"/> and <paramref name="value"/> are compared.</param>
/// </summary>
public static int IndexOf(this ReadOnlySpan<char> span, ReadOnlySpan<char> value, StringComparison comparisonType)
{
    string.CheckStringComparison(comparisonType);

    if (comparisonType == StringComparison.Ordinal)
    {
        return SpanHelpers.IndexOf(
            ref MemoryMarshal.GetReference(span),
            span.Length,
            ref MemoryMarshal.GetReference(value),
            value.Length);
    }

    switch (comparisonType)
    {
        case StringComparison.CurrentCulture:
        case StringComparison.CurrentCultureIgnoreCase:
            return CultureInfo.CurrentCulture.CompareInfo.IndexOf(span, value, string.GetCaseCompareOfComparisonCulture(comparisonType));

        case StringComparison.InvariantCulture:
        case StringComparison.InvariantCultureIgnoreCase:
            return CompareInfo.Invariant.IndexOf(span, value, string.GetCaseCompareOfComparisonCulture(comparisonType));

        default:
            Debug.Assert(comparisonType == StringComparison.OrdinalIgnoreCase);
            return CompareInfo.IndexOfOrdinalIgnoreCase(span, value, fromBeginning: true);
    }
}

可以看到，只有 StringComparison.Ordinal 下，调用了 SpanHelpers.IndexOf 方法，其余参数下依旧采用了和 string.IndexOf 一致的 CompareInfo 处理。
SpanHelpers.IndexOf

public static int IndexOf(ref byte searchSpace, int searchSpaceLength, ref byte value, int valueLength)
{
    Debug.Assert(searchSpaceLength >= 0);
    Debug.Assert(valueLength >= 0);

    if (valueLength == 0)
        return 0;  // A zero-length sequence is always treated as "found" at the start of the search space.

    byte valueHead = value;
    ref byte valueTail = ref Unsafe.Add(ref value, 1);
    int valueTailLength = valueLength - 1;
    int remainingSearchSpaceLength = searchSpaceLength - valueTailLength;

    int offset = 0;
    while (remainingSearchSpaceLength > 0)
    {
        // Do a quick search for the first element of "value".
        int relativeIndex = IndexOf(ref Unsafe.Add(ref searchSpace, offset), valueHead, remainingSearchSpaceLength);
        if (relativeIndex == -1)
            break;

        remainingSearchSpaceLength -= relativeIndex;
        offset += relativeIndex;

        if (remainingSearchSpaceLength <= 0)
            break;  // The unsearched portion is now shorter than the sequence we're looking for. So it can't be there.

        // Found the first element of "value". See if the tail matches.
        if (SequenceEqual(ref Unsafe.Add(ref searchSpace, offset + 1), ref valueTail, (nuint)valueTailLength))  // The (nunit)-cast is necessary to pick the correct overload
            return offset;  // The tail matched. Return a successful find.

        remainingSearchSpaceLength--;
        offset++;
    }
    return -1;
}

Boyer Moore

截图来自维基百科词条：博耶-穆尔字符串搜索算法

这里直接上 C# 版本源码实现

public static int BoyerMooreIndexOf(this string source, string pattern, int offset = 0, int count = -1) => BoyerMooreIndexOf(Encoding.UTF8.GetBytes(source), Encoding.UTF8.GetBytes(pattern), offset, count);

public static int BoyerMooreIndexOf(this byte[] source, byte[] pattern, int offset = 0, int count = -1)
{
    if (source == null) throw new ArgumentNullException(nameof(source));
    if (pattern == null) throw new ArgumentNullException(nameof(pattern));

    var total = source.Length;
    var length = pattern.Length;

    if (count > 0 && total > offset + count) total = offset + count;
    if (total == 0 || length == 0 || length > total) return -1;

    // 初始化坏字符，即不匹配字符
    var bads = new int[256];
    for (var i = 0; i < 256; i++)
        bads[i] = length;


    var last = length - 1;
    for (var i = 0; i < last; i++)
        bads[pattern[i]] = last - i;


    var index = offset;
    while (index <= total - length)
    {
        // 尾部开始比较
        for (var i = last; source[index + i] == pattern[i]; i--)
            if (i == 0) return index;


        // 坏字符规则：后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置
        index += bads[source[index + last]];
    }

    return -1;
}

KMP

截图来自维基百科词条：KMP算法

同样直接上源码:

 public static int KMPSearch(this string text, string pattern)
{
    var n = text.Length;
    var m = pattern.Length;

    if (n < m) return -1;
    if (n == m && text == pattern) return 0;
    if (m == 0) return 0;

    var lpsArray = new int[m];

    LongestPrefixSuffix(pattern, ref lpsArray);

    int i = 0, j = 0;
    while (i < n)
    {
        if (text[i] == pattern[j])
        {
            i++;
            j++;
        }
        if (j == m)
            return i - j;

        if (i >= n || text[i] == pattern[j]) continue;
        if (j != 0)
            j = lpsArray[j - 1];
        else
            i++;
    }

    return -1;
}

public static void LongestPrefixSuffix(string pattern, ref int[] lpsArray)
{
    var m = pattern.Length;
    var len = 0;
    lpsArray[0] = 0;
    var i = 1;

    while (i < m)
    {
        if (pattern[i] == pattern[len])
            lpsArray[i++] = ++len;
        else if (len == 0)
            lpsArray[i++] = 0;
        else
            len = lpsArray[len - 1];
    }
}

算法性能横向测试

本次横向对比了 IndexOf IndexOfOrdinal SpanIndexOf SpanIndexOfOrdinal BoyerMooreIndexOf KMPIndexOf，在查找样本长度 100, 10000, 1000000, 100000000 四种数据规模下，被查找字符串分别处于样本开头、中间、结尾、随机位置四种情况下的性能。

测试完整源码

Program.cs

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System;
using System.Collections.Generic;
using System.Text;

namespace BenchmarkSample
{
    public static class Program
    {
        [RPlotExporter]
        public class IndexOfTest
        {
            private string _haystack;
            private string _needle = "needle";

            [Params(100, 10000, 1000000, 100000000)]
            public int HaystackSize { get; set; }

            [Params(SubstringLocationEnum.Start, SubstringLocationEnum.Middle, SubstringLocationEnum.End,
                SubstringLocationEnum.Random)]
            public SubstringLocationEnum Location { get; set; }

            public IndexOfTest()
            {
                _haystack = GetRandomString(HaystackSize, _needle, Location); ;
            }

            [Benchmark]
            public int IndexOf() => _haystack.IndexOf(_needle);
            [Benchmark]
            public int IndexOfOrdinal() => _haystack.IndexOf(_needle, StringComparison.Ordinal);
            [Benchmark]
            public int SpanIndexOf() => _haystack.AsSpan().IndexOf(_needle);
            [Benchmark]
            public int SpanIndexOfOrdinal() => _haystack.AsSpan().IndexOf(_needle, StringComparison.Ordinal);
            [Benchmark]
            public int BoyerMooreIndexOf() => _haystack.BoyerMooreIndexOf(_needle);
            [Benchmark]
            public int KMPIndexOf() => _haystack.KMPSearch(_needle);

        }

        public enum SubstringLocationEnum
        {
            Start = 0, Middle, End, Random
        }

        /// <summary>
        /// 生成随机字符串并加入自定义串
        /// </summary>
        /// <param name="length">目标字符串的长度</param>
        /// <param name="custom">要插入的自定义串</param>
        /// <param name="location">插入的位置 0：开头 1：中间 2：尾部 3：随机</param>
        /// <returns></returns>
        public static string GetRandomString(int length, string custom, SubstringLocationEnum location = SubstringLocationEnum.Middle)
        => GetRandomString(length, true, true, true, true, null, custom, (int)location);

        /// <summary>
        /// 生成随机字符串 
        /// </summary>
        /// <param name="length">目标字符串的长度</param>
        /// <param name="useNum">是否包含数字，1=包含，默认为包含</param>
        /// <param name="useLow">是否包含小写字母，1=包含，默认为包含</param>
        /// <param name="useUpp">是否包含大写字母，1=包含，默认为包含</param>
        /// <param name="useSpe">是否包含特殊字符，1=包含，默认为不包含</param>
        /// <param name="customChars">要包含的自定义字符，直接输入要包含的字符列表</param>
        /// <param name="custom">要插入的自定义串</param>
        /// <param name="location">插入的位置 0：开头 1：中间 2：尾部 3：随机</param>
        /// <returns>指定长度的随机字符串</returns>
        public static string GetRandomString(int length, bool useNum = true, bool useLow = true, bool useUpp = true, bool useSpe = true, string customChars = null, string custom = null, int location = 0)
        {
            var b = new byte[4];
            new System.Security.Cryptography.RNGCryptoServiceProvider().GetBytes(b);
            Random r = new(BitConverter.ToInt32(b, 0));
            var charList = new List<char>();
            var sb = new StringBuilder();
            custom ??= string.Empty;
            charList.AddRange(custom);
            if (useNum) charList.AddRange("0123456789");
            if (useLow) charList.AddRange("abcdefghijklmnopqrstuvwxyz");
            if (useUpp) charList.AddRange("ABCDEFGHIJKLMNOPQRSTUVWXYZ");
            if (useSpe) charList.AddRange("!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~");
            var charArray = charList.ToArray();

            for (var i = 0; i < length; i++)
            {
                sb.Append(charArray[r.Next(0, charArray.Length - 1)]);
            }

            var insertIndex = location switch
            {
                0 => 0,
                1 => length / 2,
                2 => length - 1,
                3 => r.Next(0, length),
                _ => -1
            };

            return sb.Insert(insertIndex, custom).ToString();
        }

        public static int BoyerMooreIndexOf(this string source, string pattern, int offset = 0, int count = -1) => BoyerMooreIndexOf(Encoding.UTF8.GetBytes(source), Encoding.UTF8.GetBytes(pattern), offset, count);
        /// <summary>Boyer Moore 字符串搜索算法，比KMP更快，常用于IDE工具的查找</summary>
        /// <param name="source"></param>
        /// <param name="pattern"></param>
        /// <param name="offset"></param>
        /// <param name="count"></param>
        /// <returns></returns>
        public static int BoyerMooreIndexOf(this byte[] source, byte[] pattern, int offset = 0, int count = -1)
        {
            if (source == null) throw new ArgumentNullException(nameof(source));
            if (pattern == null) throw new ArgumentNullException(nameof(pattern));

            var total = source.Length;
            var length = pattern.Length;

            if (count > 0 && total > offset + count) total = offset + count;
            if (total == 0 || length == 0 || length > total) return -1;

            // 初始化坏字符，即不匹配字符
            var bads = new int[256];
            for (var i = 0; i < 256; i++)
                bads[i] = length;


            var last = length - 1;
            for (var i = 0; i < last; i++)
                bads[pattern[i]] = last - i;


            var index = offset;
            while (index <= total - length)
            {
                // 尾部开始比较
                for (var i = last; source[index + i] == pattern[i]; i--)
                    if (i == 0) return index;


                // 坏字符规则：后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置
                index += bads[source[index + last]];
            }

            return -1;
        }
        public static int KMPSearch(this string text, string pattern)
        {
            var n = text.Length;
            var m = pattern.Length;

            if (n < m) return -1;
            if (n == m && text == pattern) return 0;
            if (m == 0) return 0;

            var lpsArray = new int[m];

            LongestPrefixSuffix(pattern, ref lpsArray);

            int i = 0, j = 0;
            while (i < n)
            {
                if (text[i] == pattern[j])
                {
                    i++;
                    j++;
                }
                if (j == m)
                    return i - j;

                if (i >= n || text[i] == pattern[j]) continue;
                if (j != 0)
                    j = lpsArray[j - 1];
                else
                    i++;
            }

            return -1;
        }

        public static void LongestPrefixSuffix(string pattern, ref int[] lpsArray)
        {
            var m = pattern.Length;
            var len = 0;
            lpsArray[0] = 0;
            var i = 1;

            while (i < m)
            {
                if (pattern[i] == pattern[len])
                    lpsArray[i++] = ++len;
                else if (len == 0)
                    lpsArray[i++] = 0;
                else
                    len = lpsArray[len - 1];
            }
        }

        public static void Main(string[] args)
        {
            var summary = BenchmarkRunner.Run<IndexOfTest>();
            Console.ReadLine();
        }
    }
}

测试结果

因为测试结果比较多，生成的图表一大堆，就不放了，直接放时间表。


BenchmarkDotNet=v0.13.1, OS=Windows 10.0.22000
AMD Ryzen 7 3700X, 1 CPU, 16 logical and 8 physical cores
.NET SDK=6.0.100-preview.4.21255.9
  [Host]     : .NET 6.0.0 (6.0.21.25307), X64 RyuJIT
  DefaultJob : .NET 6.0.0 (6.0.21.25307), X64 RyuJIT

Method	HaystackSize	Location	Mean	Error	StdDev	Median
IndexOf	100	Start	1,907.369 ns	10.5384 ns	9.8576 ns	1,909.585 ns
IndexOfOrdinal	100	Start	10.262 ns	0.0898 ns	0.0750 ns	10.266 ns
SpanIndexOf	100	Start	6.445 ns	0.1105 ns	0.1033 ns	6.402 ns
SpanIndexOfOrdinal	100	Start	11.435 ns	0.1470 ns	0.1148 ns	11.426 ns
BoyerMooreIndexOf	100	Start	152.684 ns	0.8215 ns	0.6860 ns	152.648 ns
KMPIndexOf	100	Start	4.804 ns	0.0463 ns	0.0387 ns	4.797 ns
IndexOf	100	Middle	1,928.897 ns	23.5317 ns	20.8602 ns	1,928.090 ns
IndexOfOrdinal	100	Middle	10.455 ns	0.0554 ns	0.0518 ns	10.458 ns
SpanIndexOf	100	Middle	6.515 ns	0.0611 ns	0.0571 ns	6.522 ns
SpanIndexOfOrdinal	100	Middle	11.298 ns	0.0352 ns	0.0329 ns	11.296 ns
BoyerMooreIndexOf	100	Middle	152.590 ns	3.0697 ns	7.9786 ns	150.171 ns
KMPIndexOf	100	Middle	4.900 ns	0.0791 ns	0.0661 ns	4.907 ns
IndexOf	100	End	1,911.385 ns	12.0498 ns	11.2714 ns	1,908.234 ns
IndexOfOrdinal	100	End	10.713 ns	0.1678 ns	0.1401 ns	10.653 ns
SpanIndexOf	100	End	6.891 ns	0.1039 ns	0.0972 ns	6.849 ns
SpanIndexOfOrdinal	100	End	11.380 ns	0.0908 ns	0.0805 ns	11.378 ns
BoyerMooreIndexOf	100	End	149.144 ns	2.7001 ns	2.3936 ns	148.958 ns
KMPIndexOf	100	End	4.750 ns	0.0201 ns	0.0188 ns	4.753 ns
IndexOf	100	Random	1,926.007 ns	37.7531 ns	35.3143 ns	1,925.254 ns
IndexOfOrdinal	100	Random	10.446 ns	0.1609 ns	0.1427 ns	10.404 ns
SpanIndexOf	100	Random	6.384 ns	0.0295 ns	0.0261 ns	6.383 ns
SpanIndexOfOrdinal	100	Random	11.130 ns	0.0977 ns	0.0816 ns	11.109 ns
BoyerMooreIndexOf	100	Random	145.757 ns	1.7552 ns	1.4656 ns	145.716 ns
KMPIndexOf	100	Random	4.769 ns	0.0271 ns	0.0253 ns	4.770 ns
IndexOf	10000	Start	1,889.613 ns	30.0781 ns	28.1351 ns	1,876.613 ns
IndexOfOrdinal	10000	Start	10.447 ns	0.1852 ns	0.1641 ns	10.433 ns
SpanIndexOf	10000	Start	6.631 ns	0.0485 ns	0.0453 ns	6.612 ns
SpanIndexOfOrdinal	10000	Start	11.409 ns	0.0353 ns	0.0331 ns	11.413 ns
BoyerMooreIndexOf	10000	Start	149.268 ns	2.6223 ns	6.3331 ns	146.790 ns
KMPIndexOf	10000	Start	4.882 ns	0.0362 ns	0.0282 ns	4.874 ns
IndexOf	10000	Middle	1,925.414 ns	14.1439 ns	13.2303 ns	1,924.021 ns
IndexOfOrdinal	10000	Middle	10.617 ns	0.0675 ns	0.0598 ns	10.599 ns
SpanIndexOf	10000	Middle	6.610 ns	0.0871 ns	0.0772 ns	6.610 ns
SpanIndexOfOrdinal	10000	Middle	11.441 ns	0.0652 ns	0.0610 ns	11.437 ns
BoyerMooreIndexOf	10000	Middle	161.190 ns	3.1946 ns	3.2806 ns	161.188 ns
KMPIndexOf	10000	Middle	4.930 ns	0.0398 ns	0.0372 ns	4.934 ns
IndexOf	10000	End	1,924.827 ns	13.6193 ns	12.7395 ns	1,922.824 ns
IndexOfOrdinal	10000	End	10.900 ns	0.1292 ns	0.1209 ns	10.893 ns
SpanIndexOf	10000	End	6.816 ns	0.0734 ns	0.0651 ns	6.825 ns
SpanIndexOfOrdinal	10000	End	11.402 ns	0.0474 ns	0.0396 ns	11.387 ns
BoyerMooreIndexOf	10000	End	163.459 ns	3.1810 ns	3.6632 ns	162.601 ns
KMPIndexOf	10000	End	5.143 ns	0.0412 ns	0.0385 ns	5.145 ns
IndexOf	10000	Random	2,000.571 ns	39.6725 ns	38.9637 ns	2,004.035 ns
IndexOfOrdinal	10000	Random	10.909 ns	0.2449 ns	0.5723 ns	10.663 ns
SpanIndexOf	10000	Random	6.673 ns	0.0237 ns	0.0222 ns	6.666 ns
SpanIndexOfOrdinal	10000	Random	10.826 ns	0.1216 ns	0.1078 ns	10.797 ns
BoyerMooreIndexOf	10000	Random	163.361 ns	3.6494 ns	10.3528 ns	161.226 ns
KMPIndexOf	10000	Random	4.882 ns	0.0330 ns	0.0309 ns	4.872 ns
IndexOf	1000000	Start	1,917.655 ns	5.6120 ns	5.2495 ns	1,917.252 ns
IndexOfOrdinal	1000000	Start	10.716 ns	0.1213 ns	0.1135 ns	10.709 ns
SpanIndexOf	1000000	Start	6.572 ns	0.0252 ns	0.0197 ns	6.572 ns
SpanIndexOfOrdinal	1000000	Start	11.066 ns	0.0776 ns	0.0726 ns	11.066 ns
BoyerMooreIndexOf	1000000	Start	155.307 ns	3.1059 ns	3.6974 ns	156.110 ns
KMPIndexOf	1000000	Start	4.843 ns	0.0137 ns	0.0122 ns	4.846 ns
IndexOf	1000000	Middle	1,920.323 ns	18.2098 ns	17.0335 ns	1,922.634 ns
IndexOfOrdinal	1000000	Middle	10.683 ns	0.0894 ns	0.0836 ns	10.660 ns
SpanIndexOf	1000000	Middle	6.569 ns	0.0653 ns	0.0579 ns	6.570 ns
SpanIndexOfOrdinal	1000000	Middle	11.046 ns	0.0928 ns	0.0868 ns	11.040 ns
BoyerMooreIndexOf	1000000	Middle	153.735 ns	3.0260 ns	7.9716 ns	149.605 ns
KMPIndexOf	1000000	Middle	4.948 ns	0.0780 ns	0.0730 ns	4.944 ns
IndexOf	1000000	End	1,922.367 ns	15.6553 ns	13.8780 ns	1,920.379 ns
IndexOfOrdinal	1000000	End	18.310 ns	0.2918 ns	0.2730 ns	18.192 ns
SpanIndexOf	1000000	End	6.586 ns	0.0560 ns	0.0523 ns	6.580 ns
SpanIndexOfOrdinal	1000000	End	10.961 ns	0.0885 ns	0.0785 ns	10.963 ns
BoyerMooreIndexOf	1000000	End	152.627 ns	2.9601 ns	7.1490 ns	151.619 ns
KMPIndexOf	1000000	End	4.875 ns	0.0351 ns	0.0328 ns	4.859 ns
IndexOf	1000000	Random	1,911.500 ns	6.8142 ns	6.3740 ns	1,912.532 ns
IndexOfOrdinal	1000000	Random	10.602 ns	0.0849 ns	0.0752 ns	10.602 ns
SpanIndexOf	1000000	Random	6.673 ns	0.0511 ns	0.0478 ns	6.673 ns
SpanIndexOfOrdinal	1000000	Random	11.070 ns	0.1190 ns	0.1113 ns	11.049 ns
BoyerMooreIndexOf	1000000	Random	149.230 ns	3.0118 ns	5.0320 ns	147.710 ns
KMPIndexOf	1000000	Random	4.858 ns	0.0327 ns	0.0290 ns	4.859 ns
IndexOf	100000000	Start	1,915.633 ns	14.4868 ns	13.5510 ns	1,917.496 ns
IndexOfOrdinal	100000000	Start	10.772 ns	0.1435 ns	0.1342 ns	10.764 ns
SpanIndexOf	100000000	Start	6.827 ns	0.0666 ns	0.0623 ns	6.806 ns
SpanIndexOfOrdinal	100000000	Start	10.977 ns	0.0593 ns	0.0526 ns	10.989 ns
BoyerMooreIndexOf	100000000	Start	146.921 ns	2.9779 ns	2.6398 ns	147.245 ns
KMPIndexOf	100000000	Start	4.833 ns	0.0151 ns	0.0134 ns	4.832 ns
IndexOf	100000000	Middle	1,906.318 ns	5.4295 ns	5.0788 ns	1,905.934 ns
IndexOfOrdinal	100000000	Middle	10.725 ns	0.2305 ns	0.2467 ns	10.689 ns
SpanIndexOf	100000000	Middle	6.862 ns	0.0724 ns	0.0642 ns	6.851 ns
SpanIndexOfOrdinal	100000000	Middle	11.001 ns	0.0903 ns	0.0845 ns	11.019 ns
BoyerMooreIndexOf	100000000	Middle	152.705 ns	2.4382 ns	2.2807 ns	152.401 ns
KMPIndexOf	100000000	Middle	4.850 ns	0.0262 ns	0.0245 ns	4.846 ns
IndexOf	100000000	End	1,923.149 ns	9.6492 ns	9.0258 ns	1,921.531 ns
IndexOfOrdinal	100000000	End	10.718 ns	0.1682 ns	0.1491 ns	10.759 ns
SpanIndexOf	100000000	End	6.807 ns	0.0234 ns	0.0207 ns	6.804 ns
SpanIndexOfOrdinal	100000000	End	11.071 ns	0.1070 ns	0.1001 ns	11.076 ns
BoyerMooreIndexOf	100000000	End	147.044 ns	2.9552 ns	2.7643 ns	147.472 ns
KMPIndexOf	100000000	End	4.966 ns	0.1067 ns	0.0891 ns	4.949 ns
IndexOf	100000000	Random	1,925.095 ns	30.9030 ns	28.9067 ns	1,923.878 ns
IndexOfOrdinal	100000000	Random	10.486 ns	0.0910 ns	0.0806 ns	10.498 ns
SpanIndexOf	100000000	Random	7.009 ns	0.1658 ns	0.1628 ns	7.015 ns
SpanIndexOfOrdinal	100000000	Random	11.080 ns	0.0898 ns	0.0840 ns	11.112 ns
BoyerMooreIndexOf	100000000	Random	155.551 ns	3.1132 ns	4.2614 ns	155.335 ns
KMPIndexOf	100000000	Random	4.887 ns	0.0573 ns	0.0536 ns	4.871 ns

总结

不同算法在数据集大小不同和关键字符串位置不同的情况下，表现都很稳定。
默认的 IndexOf 最好使用 StringComparison.Ordinal ，比默认的 StringComparison.CurrentCulture 快两个数量级，平均大约是 20 倍的差距。
算法效率由快到慢排序为 KMPIndexOf SpanIndexOf IndexOfOrdinal SpanIndexOfOrdinal BoyerMooreIndexOf IndexOf，效率比率大约为：

KMPIndexOf	SpanIndexOf	IndexOfOrdinal	SpanIndexOfOrdinal	BoyerMooreIndexOf	IndexOf
1	2	2.5	3	35	200

PS：以上结果仅为本人测试所得，供本人日后编程参考，不排除有代码 BUG 的可能，欢迎斧正。