c# - 计算子串的算法

Question

我正在努力学习制作有效的算法。我查找子字符串的代码如下

 public static bool HasSubstring(string MainStr,string SubStr)
    {
        bool FoundMatch = false;

        for (int i = 0; i < MainStr.Length; i++)
        {

            if (SubStr.Length != 0)
            {
                int a = 0;
                int j = 0;
                if (MainStr[i] == SubStr[a])
                {
                    j = i;
                    do
                    {
                        if (MainStr[j] == SubStr[a])
                        {
                            a++;
                            j++;
                            FoundMatch = true;
                            continue;

                        }
                        else
                        {
                            FoundMatch = false;
                            break;
                        }


                    } while (a<SubStr.Length);
                    if (FoundMatch == true)
                    {
                        break;
                    }


                }
            }
        }

        return FoundMatch;


    }

我可以优化这种方法吗？

Answer 1

我可以看到一些事情来改善这一点

• 在循环之前，检查子字符串是否为 0 长度，如果是则返回 false（不要检查每次迭代）
• 删除ALL == true基本上是将布尔值与布尔值进行比较
• 使用IndexOf查找子字符串的第一个字符（如果 indexOf 的结果为 -1，则返回 false），然后将此索引用作 i 的起始值

• 我相信j你可以增加变量而不是变量，i但我没有测试过这个

  if (FoundMatch)
    return true;
  

Answer 2

我认为您可以查看以下算法：

• 克努斯·莫里斯·普拉特
• 拉宾-卡普

如果您想查找所有出现的子字符串，这些是用于字符串中模式匹配的一些众所周知的算法。

Answer 3

使用 Wile 而不是 Do While。两个循环之间的区别在于，Do 循环中的代码将至少执行一次，因为 while 部分位于末尾。在开头的 while 部分，圆括号中的结束条件可能已经为真（我可能不仅仅是 loopEnd）。我认为你不需要继续。