kmp（题目连接）
分析
简化字符串匹配的暴力解法 通过求解ne数组，找到每一个字符之前的串中前缀==后缀的最大长度 每次 j 指针向右一定ne[j]位即可 省去不必要的循环
代码
#include <bits/stdc++.h>
using namespace std
;
const int N
= 1e5+10, M
= 1e6+10;
char p
[N
], s
[M
];
int ne
[N
];
int main()
{
int n
, m
;
cin
>> n
>> p
+ 1 >> m
>> s
+ 1;
for (int i
= 2, j
= 0; i
<= n
; i
++)
{
while (j
&& p
[i
] != p
[j
+ 1])
j
= ne
[j
];
if (p
[i
] == p
[j
+ 1])
j
++;
ne
[i
] = j
;
}
for (int i
= 1, j
= 0; i
<= m
; i
++)
{
while (j
&& s
[i
] != p
[j
+ 1])
j
= ne
[j
];
if (s
[i
] == p
[j
+ 1])
j
++;
if (j
== n
)
{
printf("%d ", i
- n
);
j
= ne
[j
];
}
}
return 0;
}
