本文共 636 字,大约阅读时间需要 2 分钟。
前缀函数主要是求出模式串中的next数组,那么什么是模式串呢?模式串模式串的概念很简单。举个例子:“给出一个字符串 T,再给出 n 个字符串 S1、S2...Sn,问 S1、S2...Sn 中有哪些是 T 的子串?”在这个例子中,S1、S2...Sn 便是 n 个模式串,T便是被匹配串。模式串是用来与被匹配串匹配的。
next数组的主要意义是: 若模式串 P 的前 i 个字符组成的子串为S,那么S的前next[i]个字符’与‘S的后 next[i]个字符’相同。 如果理解了这个意思,那么这个前缀函数的模板就很好看懂了。 模板: -
-
-
- void COMPUTE_PREFIX_FUNCTION(char P[])
- {
- int m=strlen(P+1);
- next[1]=0;
- for(int k=0,q=2;q<=m;q++)
-
- {
- while(k>0&&P[k+1]!=P[q])
- k=next[k];
- if(P[k+1]==P[q])
- k++;
- next[q]=k;
- }
- }
转载地址:http://gpali.baihongyu.com/