c++ 如果不使用find()函数,我怎么知道一个子串是否存在于一个字符串中?

vhmi4jdf  于 2023-02-20  发布在  其他
关注(0)|答案(1)|浏览(107)

如果不使用find()函数,我怎样才能找到一个子字符串是否存在于字符串中?有没有比使用find()函数更有效的方法来找到子字符串?

#include <bits/stdc++.h>
using namespace std;

int isSubstring(string s1, string s2)
{
     int M = s1.length();
     int N = s2.length();
     for (int i = 0; i <= N - M; i++) {
          int j;
      for (j = 0; j < M; j++)
        if (s2[i + j] != s1[j])
            break;

      if (j == M)
        return i;
     }

     return -1;
}

int main()
{
     string s1 = "for";
     string s2 = "geeksforgeeks";
     int res = isSubstring(s1, s2);
     if (res == -1)
    cout << "Not present";
     else
    cout << "Present at index " << res;
     return 0;
}

//我在Geeks for geeks上找到了这段代码,但是它的时间复杂度是O(M*(N-M)),可以降低吗?

kr98yfug

kr98yfug1#

当然,您可以迭代一个字符串,并将每个可能的子字符串与要搜索的子字符串进行比较。

但是一般来说,使用STL中的方法更好,因为它们经过了良好的测试,并且在大多数情况下比您自己的实现更快。

相关问题