LeetCode 0028 - Implement strStr()
# Hints
水题
KMP
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Easy | or |
Implement strStr()
.
Return the index of the first occurrence of needle in haystack, or 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()
and Java's indexOf()
.
# 题意
给定两个字符串 haystack
和 needle
,求 needle
在 haystack
中首次出现的下标,如果未出现则返回 。
# 题解
字符串的单模式匹配问题,对于本题而言,暴力求解和KMP算法均可。
由于本题数据量太小,考虑到常数的原因,KMP的运行速度甚至未必有暴力求解更高,但性能优越的KMP算法仍然是有必要掌握的。
细节问题:
- 当
needle
为空时应当返回 是合理的。
# AC代码(暴力求解)
class Solution {
public:
int strStr(string haystack, string needle) {
// ����
if (needle.length() == 0) {
return 0;
}
// ���
int n = haystack.length(), m = needle.length();
for (int t = 0; t + m - 1 < n; t ++) {
// ƥ��
int i = t, j = 0;
while (j < m && haystack[i] == needle[j]) {
i ++;
j ++;
}
// ƥ��ɹ������
if (j == m) {
return t;
}
}
// ����
return -1;
}
};
# AC代码(KMP)
class Solution {
public:
int strStr(string haystack, string needle) {
// ����
if (needle.length() == 0) {
return 0;
}
// ��ʼ��
int fail[needle.length() + 5];
// KMP
make_fail(needle, fail);
return kmp(haystack, needle, fail);
}
// ����fail����
void make_fail(const string & mode, int fail[]) {
// ��ʼ��
fail[0] = 0;
// ����
for (int i = 1, j = 0; i < mode.length(); i ++) {
while (j > 0 && mode[i] != mode[j]) {
j = fail[j - 1];
}
if (mode[i] == mode[j]) {
fail[i] = ++j;
} else {
fail[i] = 0;
}
}
}
// KMP
int kmp(const string & str, const string & mode, int fail[]) {
// ����
for (int i = 0, j = 0; i < str.length(); i ++) {
while (j > 0 && str[i] != mode[j]) {
j = fail[j - 1];
}
if (str[i] == mode[j]) {
j ++;
}
if (j == mode.length()) {
return (i - mode.length() + 1);
}
}
// ����
return -1;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01