#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e3+10,inf = 0x3f3f3f3f; int nex[N]; //nex[j]的意思是当子串的第j个字符和主串的第i个字符不匹配时,我们应该从子串的nex[j]字符开始重新匹配 string a,b; /* kmp指针回退 j = nex[j - 1] 根本原因:子串的指针j总是表示我们即将要匹配子串的第j个字符,所以如果子串[j]和主串[i]不匹配 那么我们自然是要从子串的nex[j - 1]字符开始重新匹配 */ void get_next(string b) { int j = 0; //前缀末尾 for(int i = 1; i < b.size(); i++) { //指针回退 while(j > 0 && b[i] != b[j]) j = nex[j - 1]; //前缀和后缀的末尾相同则计数 if(b[j] == b[i]) j++; nex[i] = j; } } int kmp(string a,string b) //获取子串在主串中第一次出现的位置 { int j = 0; //子串指针j,主串指针i for(int i = 0; i < a.size(); i++) { while(j > 0 && a[i] != b[j]) j = nex[j - 1]; //3.指针回退 if(a[i] == b[j]) j++; //1.当前子串和主串匹配,那么继续匹配子串的下一个 if(j == b.size()) //2.如果匹配完了,那么成功匹配的位置是:主串当前长度i - 子串长度b.size() + 1 { //这里是返回子串在主串中第一次出现的位置,如果要解决其他问题,可以在这里进行修改 return i - b.size() + 1; } } return -1; //没有匹配成功返回-1 } int main() { getline(cin,a); getline(cin,b); get_next(b); cout << kmp(a,b); return 0; }
标签:子串,主串,匹配,int,nex,KMP,模板,size From: https://www.cnblogs.com/jyssh/p/17846966.html