题解 | 串的模式匹配
串的模式匹配
https://www.nowcoder.com/practice/084b6cb2ca934d7daad55355b4445f8a
解题思路
这是一个字符串匹配问题，需要在字符串 中找到字符串
第一次出现的位置。可以使用
算法来高效解决。
关键点：
- 构建
算法的
数组
- 利用
- 处理边界情况
算法步骤：
- 计算模式串
的
- 在主串
中进行匹配
- 找到匹配位置或返回-1
代码
class StringPattern {
public:
vector<int> getNext(const string& pattern) {
int n = pattern.length();
vector<int> next(n, 0);
for (int i = 1, j = 0; i < n; i++) {
while (j > 0 && pattern[i] != pattern[j]) {
j = next[j - 1];
}
if (pattern[i] == pattern[j]) {
j++;
}
next[i] = j;
}
return next;
}
int findAppearance(string A, int lena, string B, int lenb) {
if (lenb == 0) return 0;
if (lena < lenb) return -1;
vector<int> next = getNext(B);
for (int i = 0, j = 0; i < lena; i++) {
while (j > 0 && A[i] != B[j]) {
j = next[j - 1];
}
if (A[i] == B[j]) {
j++;
}
if (j == lenb) {
return i - lenb + 1;
}
}
return -1;
}
};
import java.util.*;
public class StringPattern {
private int[] getNext(String pattern) {
int n = pattern.length();
int[] next = new int[n];
for (int i = 1, j = 0; i < n; i++) {
while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
j = next[j - 1];
}
if (pattern.charAt(i) == pattern.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}
public int findAppearance(String A, int lena, String B, int lenb) {
if (lenb == 0) return 0;
if (lena < lenb) return -1;
int[] next = getNext(B);
for (int i = 0, j = 0; i < lena; i++) {
while (j > 0 && A.charAt(i) != B.charAt(j)) {
j = next[j - 1];
}
if (A.charAt(i) == B.charAt(j)) {
j++;
}
if (j == lenb) {
return i - lenb + 1;
}
}
return -1;
}
}
class StringPattern:
def getNext(self, pattern):
n = len(pattern)
next = [0] * n
j = 0
for i in range(1, n):
while j > 0 and pattern[i] != pattern[j]:
j = next[j - 1]
if pattern[i] == pattern[j]:
j += 1
next[i] = j
return next
def findAppearance(self, A, lena, B, lenb):
if lenb == 0:
return 0
if lena < lenb:
return -1
next = self.getNext(B)
j = 0
for i in range(lena):
while j > 0 and A[i] != B[j]:
j = next[j - 1]
if A[i] == B[j]:
j += 1
if j == lenb:
return i - lenb + 1
return -1
算法及复杂度
- 算法：KMP字符串匹配
- 时间复杂度：
，其中
是主串长度，
是模式串长度
- 空间复杂度：
，用于存储
查看3道真题和解析
，不说了，我又接了一单