#209-[KMP]字符串匹配
Description
来自传题者的善意
-
Sample Input
来自传题者的善意
-
Sample Output
HINT
Uploaded By MCHacker
样例的一个输出数有误,应该是-1。
求模式串在文本串中的第一次出现位置,可以用KMP。
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
using namespace std;
vector<int> get_next(string s) { // 得到next数组
vector<int> nxt; nxt.push_back(-1); // 由于下标从0开始,这里每个next都减去了1。
int id = -1, n = s.size();
for (int i=1; i<n; ++i) { // 模式串自己和自己匹配
while ((id>=0) && (s[i]!=s[id+1])) id = nxt[id]; // 如果不匹配,就往回跳到next,id<0时强制停止
/*
0 nxt[j]-1 j-1 j=nxt[i] i-j i-1 i
t #################---------------------------#################-- (#部分相等)
0 nxt[j]-1 j-1 j=nxt[i] i-j i-nxt[j] i-1 i
t *********########---------------------------#####************-- (*部分相等)
*/
if (s[i]==s[id+1]) ++id; // 匹配,nxt加一
nxt.push_back(id);
}
return nxt;
}
vector<int> find_pos(vector<int> nxt, string s, string s2) { // 找所有位置
vector<int> res;
int id = -1, n = s.size(), n2 = s2.size();
for (int i=0; i<n; ++i) { // 模式串和文本串匹配,原理同上
while ((id>=0) && (s[i]!=s2[id+1])) id = nxt[id];
if (s[i]==s2[id+1]) ++id;
if (id+1==n2) { // 找到匹配
res.push_back(i-n2+1); id = nxt[id]; // 得到位置,id回退
}
}
return res;
}
vector<int> kmp_find(string text_str, string search_str) {
return find_pos(get_next(search_str), text_str, search_str);
}
int main() {
int t; scanf("%d", &t);
for (int i=1; i<=t; ++i) {
string s, s2; cin >> s >> s2;
vector<int> res = kmp_find(s, s2);
printf("Case #%d: %d\n", i, (res.size()) ? res[0] : -1);
}
return 0;
}