[LeetCode & 剑指 offer 刷题笔记] 目录 (持续更新中...)
- Implement strStr()
- Implement strStr() http://www.cplusplus.com/reference/cstring/strstr/ .
- Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
- Example 1:
- Input: haystack = "hello", needle = "ll"
- Output: 2
- Example 2:
- Input: haystack = "aaaaa", needle = "bba"
- Output: -1
- Clarification:
- What should we return when needle
is an empty string? This is a great question to ask during an interview.
- For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() http://www.cplusplus.com/reference/cstring/strstr/ and Java's indexOf().
- // 问题: 实现 strstr 函数, 子串查找 (子串匹配)
- // 方法一: 扫描主串, 再扫描子串, O(mn)
- #include <string>
- class Solution
- {
- public:
- int strStr(string haystack, string needle)
- {
- int m = haystack.size(), n = needle.size();
- if(n == 0) return 0; // 如果 needle 为空
- /* int result = haystack.find(needle);
- if(result != string::npos) return result;
- else return -1;*/
- for(int i = 0; i <= m-n; i++) // 扫描主串, 最后一个位置起始索引为 m-n, i = 0~m-n
- {
- int j =0;
- for(; j<n; j++) // 扫描子串, j=0~n-1
- {
- if(haystack[i+j]!=needle[j])
- break; // 如果有某个字符不匹配则退出循环
- }
- if(j == n) return i; // 如果均匹配, 返回子串在主串中的起始索引
- }
- return -1; // 如果未找到, 则返回 - 1
- }
- };
- // 方法二: KMP 算法 (子串匹配的更高效算法)
来源: http://www.bubuko.com/infodetail-2909538.html