gpt-3.5-turbo-0301· OpenAI WildChat-4.8M (AI2)
void getnext(SString T, int &next[ ] ){ //求模式串T的next函数值并存入数组next[ ] i=1; j=0; next[1]=0;…
- User
void get_next(SString T, int &next[ ] ){ //求模式串T的next函数值并存入数组next[ ] i=1; j=0; next[1]=0; while(i<T[0] ){ //T[0]为T串之长度 if(j= = 0||T[i]= =T[j]) {++i; ++j; next[i]=j;} //首次必j=0 else j=next[j]; } }// get_next
- Assistant
(SString T, int &next[]) 的功能是求出模式串 T 的 next 数组值,并将其存入数组 next[]。该算法采用了 KMP 字符串匹配算法中的 next 数组求解方法,具体实现如下:
1.初始化 i 为 1,j 为 0, next[1] 为 0。 2.对于 i = 2 到 T[0](T[0] 为模式串 T 的长度),执行如下操作: (1)如果 j = 0,或者 T[i] = T[j],则令 i 和 j 分别加 1,并将 next[i] 的值赋为 j+1。 (2)如果 T[i] != T[j],则将 j 赋值为 next[j],并重复(1)操作。 3.求解完成后,将 next 数组返回。