描述
判断一个字符串是否是另一个字符串的子串；
分析
采用暴力方法进行查找：
1，计算出待查找子串的长度；
2，使用两个指针在源字符串标识出开始结尾的元素；
3，在标识出的区域依次和待查找子串进行比较；
4，完全匹配，则返回源字符串的开始位置；
5，不匹配，则前移源字符串中的开始、结尾元素指针；
实现
// Implement strStr
char *strStr(const char *haystack, const char *needle)
{
// 标识源字符串的查找范围
const char *pBeginSrc = haystack;
const char *pEnd = haystack;
const char *ptag = &needle[1];
while (*ptag) {
++pEnd;
++ptag;
}
// 开始在源字符串匹配子串
for (; *pEnd; ++pEnd) {
char *pOldBegin = (char *)pBeginSrc;
const char *p2 = needle;
while (*pBeginSrc && *p2 && *pBeginSrc==*p2) {
++pBeginSrc;
++p2;
}
if (!*p2) {
return pOldBegin;
}
pBeginSrc = pOldBegin + 1;
}
return nullptr;
}
时间复杂度为O(mxn)，空间复杂度为O(1)。
