题目链接：【模板】KMP - 洛谷
注意:
1、next数组是针对子串的，并未涉及母串，因此求next数组时与母串无关 2、在KMP算法中，字符串的起始下标为1，这样子方便操作，因此我们读入s母串和p子串后，要s = '0' s; p = '0' p
求解字符串的next数组，要提前知道next数组的变化规律
next数组的变化规律：
1、若j的位置和i的位置匹配上了，则next[j 1] = next[j] 1，注意如果匹配上了，next数组一定是 1递增的，跨度只能是1 2、若j的位置和i的位置没匹配上，则j = next[j]，回退到next[j]的位置
初始化：
求next数组部分：
1、该部分只涉及子串 2、next[1] = 0; 3、for遍历i，只走一次，不回退，且i初始化为2，因为next[1]已经被定义了 4、j从0开始
KMP部分：
1、for遍历i，只走一次，不回退，i初始化为1（注意这里和next数组的不同），且for用来遍历母串 2、j从0开始，遍历的是子串
AC代码：
代码语言：javascript复制const int N = 1e6 5;
int nextt[N];
void GetNext(const string& p)
{
nextt[1] = 0;
int n = p.size() - 1;//因为在字符串前面加了个'0'，所以字符串的长度 = 字符串的size - 1
for (int i = 2, j = 0/**/; i <= n; i )
{
while (j && p[j 1] != p[i])
/*注意有一个 1，要判断的是下一个位置是否和i位置相等*/
j = nextt[j];//回退
if (p[j 1] == p[i])//如果匹配上了
j ;//继续往后走，不回退
nextt[i] = j;//注意是next[i]，并不是next[j]
}
}
void KMP(const string& s, const string& p)
{
int len1 = s.size() - 1;
int len2 = p.size() - 1;//因为在字符串前面加了个'0'，所以字符串的长度 = 字符串的size - 1
for (int i = 1/**/, j = 0; i <= len1/*注意是遍历母串*/; i )
{
while (j && p[j 1] != s[i]/*子串的j 1和母串的i不匹配*/)
j = nextt[j];//回退
if (p[j 1] == s[i])//如果匹配上了
j ;//继续往后走，不回退
//题目要求的输出
if (j == len2)
cout << i - len2 1 << endl;
}
}
void solve()
{
string s, p;//母串，子串（模式串）
cin >> s >> p;
s = '0' s;//注意下标从1开始
p = '0' p;
GetNext(p);
KMP(s, p);
int len1 = s.size();
int len2 = p.size();
for (int i = 1/*从1开始*/; i < len2; i )
cout << nextt[i] << " ";
cout << endl;
}
int main()
{
solve();
return 0;
}
