描述
判斷一個(gè)字符串是否是另一個(gè)字符串的子串垮抗；
分析
采用暴力方法進(jìn)行查找：
1，計(jì)算出待查找子串的長(zhǎng)度舷蟀；
2，使用兩個(gè)指針在源字符串標(biāo)識(shí)出開(kāi)始結(jié)尾的元素面哼；
3野宜，在標(biāo)識(shí)出的區(qū)域依次和待查找子串進(jìn)行比較；
4魔策，完全匹配匈子，則返回源字符串的開(kāi)始位置；
5闯袒，不匹配虎敦，則前移源字符串中的開(kāi)始、結(jié)尾元素指針政敢；
實(shí)現(xiàn)
// Implement strStr
char *strStr(const char *haystack, const char *needle)
{
// 標(biāo)識(shí)源字符串的查找范圍
const char *pBeginSrc = haystack;
const char *pEnd = haystack;
const char *ptag = &needle[1];
while (*ptag) {
++pEnd;
++ptag;
}
// 開(kāi)始在源字符串匹配子串
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;
}
時(shí)間復(fù)雜度為O(mxn)原茅，空間復(fù)雜度為O(1)。
