diff options
author | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
commit | 7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch) | |
tree | eb7a24ee2067f92245c57bb118e85a1baf15df50 /other/idx_first_occur_str.cpp | |
parent | 5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff) | |
download | leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip |
chore: move cpp and rust code to directory
Diffstat (limited to 'other/idx_first_occur_str.cpp')
-rw-r--r-- | other/idx_first_occur_str.cpp | 51 |
1 files changed, 51 insertions, 0 deletions
diff --git a/other/idx_first_occur_str.cpp b/other/idx_first_occur_str.cpp new file mode 100644 index 0000000..0f24457 --- /dev/null +++ b/other/idx_first_occur_str.cpp @@ -0,0 +1,51 @@ +// 28. Find the Index of the First Occurrence in a String +#include "leetcode.h" +#include <vector> + +/* + * given two strings 'needle' and 'haystack', return index of the first + * occurrence of 'needle' in 'haystack', or -1 if 'needle' is not part of + * 'haystack' + */ + +class Solution { +public: + int strStr(string haystack, string needle) { + int m = haystack.size(), n = needle.size(); + if (!n) + return 0; + vector<int> lps = kmp(needle); + for (int i = 0, j = 0; i < m;) { + if (haystack[i] == needle[j]) + i++, j++; + if (j == n) + return i - j; + if (i < m && haystack[i] != needle[j]) + j ? j = lps[j - 1] : i++; + } + return -1; + } + +private: + // kmp algorithm: + // http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/ + vector<int> kmp(string needle) { + int n = needle.size(); + vector<int> lps(n, 0); + for (int i = 1, len = 0; i < n;) { + if (needle[i] == needle[len]) + lps[i++] = ++len; + else if (len) + len = lps[len - 1]; + else + lps[i++] = 0; + } + return lps; + } +}; + +int main() { + Solution obj; + cout << obj.strStr("sadbutsad", "sad") << endl; // expect: 0 + cout << obj.strStr("leetcode", "leeto") << endl; // expect: -1 +} |