题目描述
终于懂了,理解万岁,
y总的三刷,b站王卓老师讲的二刷,我感觉二者讲的侧重点不同,y总的针对于本质,王卓老师针对于公式.
而那个公式的由来其实就是y总讲到的:一个模板串上”看对眼看不对眼”的问题,针对代码就是 p[i] 和 p[j + 1]的情况
样例
#include <iostream>
using namespace std;
const int M = 1000010,N = 100010;
int n,m;
char s[M],p[N];
int ne[N];
int main()
{
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){//模式串P在S种所有出现的位置的起始下标,一结束就可以了,
printf("%d ",i - j);//因为开始的时候是一起走
j = ne[j];//归零
}
}
}
字符串建议一口气学到SAM (doge)