如果不使用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)),可以降低吗?
1条答案
按热度按时间kr98yfug1#
当然,您可以迭代一个字符串,并将每个可能的子字符串与要搜索的子字符串进行比较。
但是一般来说,使用STL中的方法更好,因为它们经过了良好的测试,并且在大多数情况下比您自己的实现更快。