计算子字符串的算法

本文关键字：算法 字符串 计算 | 更新日期: 2023-09-27 18:17:31

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

 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;

    }

我可以优化这个方法吗?

计算子字符串的算法

我可以看到一些事情来改进这个

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

  • 我相信除了j变量你可以增加i但是我还没有测试过这个

    if (FoundMatch)
  return true;

我想你可以看看下面的算法:

  • Knuth Morris Pratt
  • - karp

如果你想找到一个字符串中所有出现的子字符串，下面是一些众所周知的模式匹配算法。

使用While代替Do While。这两个循环的不同之处在于Do循环中的代码将至少执行一次，因为while部分在末尾。while部分位于开头，圆括号中的结束条件可能已经为真(i可能大于loopEnd)。我觉得你没必要继续了。

相关文章：