D 语言高效字符串替换算法实现 - 无需标准库函数

以下是两种更高效的实现方式：

1. Boyer-Moore 字符串匹配算法

Boyer-Moore 算法是一种高效的字符串匹配算法，它可以在 O(n) 的时间内完成字符串匹配，其中 n 是主串的长度。该算法的核心思想是利用模式串中的信息来跳过尽可能多的无效比较，从而提高匹配效率。

在本题中，我们可以将搜索子串作为模式串，主串作为文本串，利用 Boyer-Moore 算法来进行字符串替换。具体实现过程如下：

template <typename T>
ref string replaceString(auto ref allStr, auto ref searchStr, auto ref replaceStr, bool isCaseSensitive = true)
if (isSomeString!T)
{
    if (!isCaseSensitive)
    {
        allStr = allStr.toLower;
        searchStr = searchStr.toLower;
    }

    size_t n = allStr.length;
    size_t m = searchStr.length;

    // 计算坏字符表
    int bc[256];
    for (int i = 0; i < 256; i++)
        bc[i] = -1;
    for (int i = 0; i < m; i++)
        bc[searchStr[i]] = i;

    // 计算好后缀表
    int gs[m];
    int suff[m];
    suff[m - 1] = m;
    int f = 0, g;
    for (int i = m - 2; i >= 0; i--)
    {
        if (i > f && suff[m - 1 - f + i] < i - f)
            suff[i] = suff[m - 1 - f + i];
        else
        {
            if (i < f)
                f = i;
            g = f - i;
            while (f >= 0 && searchStr[f] == searchStr[m - 1 - g + f])
                f--;
            suff[i] = g - f;
        }
    }
    for (int i = 0; i < m; i++)
        gs[i] = m;
    int j = 0;
    for (int i = m - 1; i >= -1; i--)
    {
        if (i == -1 || suff[i] == i + 1)
        {
            for (; j < m - 1 - i; j++)
                if (gs[j] == m)
                    gs[j] = m - 1 - i;
        }
    }
    for (int i = 0; i <= m - 2; i++)
        gs[m - 1 - suff[i]] = m - 1 - i;

    // 开始匹配
    size_t i = 0;
    while (i <= n - m)
    {
        int j = m - 1;
        while (j >= 0 && searchStr[j] == allStr[i + j])
            j--;
        if (j < 0)
        {
            allStr = allStr[0 .. i] ~ replaceStr ~ allStr[i + m .. $];
            i += replaceStr.length;
        }
        else
        {
            int x = j - bc[allStr[i + j]];
            int y = 0;
            if (j < m - 1)
                y = gs[j + 1];
            i += std.max(x, y);
        }
    }

    return allStr;
}

2. KMP 字符串匹配算法

KMP 算法是另一种高效的字符串匹配算法，它也可以在 O(n) 的时间内完成字符串匹配。该算法的核心思想是利用模式串中的前缀和后缀的信息来跳过尽可能多的无效比较，从而提高匹配效率。

在本题中，我们同样可以将搜索子串作为模式串，主串作为文本串，利用 KMP 算法来进行字符串替换。具体实现过程如下：

template <typename T>
ref string replaceString(auto ref allStr, auto ref searchStr, auto ref replaceStr, bool isCaseSensitive = true)
if (isSomeString!T)
{
    if (!isCaseSensitive)
    {
        allStr = allStr.toLower;
        searchStr = searchStr.toLower;
    }

    size_t n = allStr.length;
    size_t m = searchStr.length;

    // 计算 next 数组
    int next[m];
    next[0] = -1;
    int i = 0, j = -1;
    while (i < m - 1)
    {
        if (j == -1 || searchStr[i] == searchStr[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
            j = next[j];
    }

    // 开始匹配
    i = 0;
    while (i <= n - m)
    {
        j = 0;
        while (j < m && searchStr[j] == allStr[i + j])
            j++;
        if (j == m)
        {
            allStr = allStr[0 .. i] ~ replaceStr ~ allStr[i + m .. $];
            i += replaceStr.length;
        }
        else
            i += std.max(1, j - next[j]);
    }

    return allStr;
}