求子串在主串中的位置
时间: 2023-12-06 09:44:20 浏览: 52
可以使用字符串匹配算法来求解子串在主串中的位置。其中最经典的算法是KMP算法。
KMP算法的核心思想是利用已经匹配过的信息,避免在匹配过程中出现重复的比较。具体来说,首先预处理出模式串的最长公共前后缀长度LPS数组,然后在匹配过程中,当匹配失败时,利用LPS数组中记录的已匹配前缀信息,将模式串向右移动尽可能少的距离,使得模式串中该位置之前的字符都能匹配成功,从而避免了不必要的比较。
下面是KMP算法的C++代码实现:
```cpp
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> computeLPS(const string& pattern) {
int n = pattern.size();
vector<int> lps(n, 0);
int i = 1, j = 0;
while (i < n) {
if (pattern[i] == pattern[j]) {
lps[i++] = ++j;
} else if (j > 0) {
j = lps[j - 1];
} else {
i++;
}
}
return lps;
}
int kmp(const string& text, const string& pattern) {
int m = text.size(), n = pattern.size();
vector<int> lps = computeLPS(pattern);
int i = 0, j = 0;
while (i < m) {
if (text[i] == pattern[j]) {
i++, j++;
if (j == n) {
return i - j;
}
} else if (j > 0) {
j = lps[j - 1];
} else {
i++;
}
}
return -1;
}
int main() {
string text = "ABABDABACDABABCABAB", pattern = "ABABCABAB";
int pos = kmp(text, pattern);
if (pos != -1) {
cout << "Pattern found at position " << pos << endl;
} else {
cout << "Pattern not found" << endl;
}
return 0;
}
```
在上面的代码中,computeLPS函数用于预处理模式串的LPS数组,kmp函数用于实现KMP算法,并返回子串在主串中的位置。需要注意的是,如果子串不在主串中出现,则kmp函数返回-1。