KMP算法

    xiaoxiao2022-07-05  187

    KMP算法

    在一个字符串S(原串)内查找一个模式串P(字串)的出现位置。 关于next[] 例: 模式串 P=“ababababca” 的部分匹配函数与next函数

    可直接使用
    void GetNext(char* p, int next[]) { int pLen = strlen(p); next[0] = -1; int k = -1; int j = 0; while (j < pLen - 1) { //p[k]表示前缀,p[j]表示后缀 if (k == -1 || p[j] == p[k]) { ++k; ++j; next[j] = k; } else { k = next[k]; } } } int KmpSearch(char* s, char* p) { int i = 0; //主串中字符的移动标识i int j = 0; //子串中字符的移动标识j int sLen = strlen(s);//主串字符个数 int pLen = strlen(p);//子串字符个数 int next[255]; //next数组,记录子串的移动规则 GetNext(p, next); while (i < sLen && j < pLen) { //如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++ if (j == -1 || s[i] == p[j]) { i++; j++; } else { //如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j] //next[j]即为j所对应的next值 j = next[j]; } } if (j == pLen)//在主串中找到子串 return i - j; else return -1;//没找到返回-1 } /* * next[] 的含义:x[i-next[i]...i-1]=x[0...next[i]-1] * next[i] 为满足 x[i-z...i-1]=x[0...z-1] 的最大 z 值(就是 x 的自身匹配) */ void kmp_pre(char x[],int m,int next[]) { int i,j; j=next[0]=-1; i=0; while(i<m) { while(-1!=j && x[i]!=x[j]) j=next[j]; next[++i]=++j; } } /* * kmpNext[i] 的意思:next'[i]=next[next[...[next[i]]]](直到 next'[i]<0 或者 x[next'[i]]!=x[i]) * 这样的预处理可以快一些 */ void preKMP(char x[],int m,int kmpNext[]) { int i,j; j=kmpNext[0]=-1; i=0; while(i<m) { while(-1!=j && x[i]!=x[j])j=kmpNext[j]; if(x[++i]==x[++j])kmpNext[i]=kmpNext[j]; else kmpNext[i]=j; } } /* * 返回 x 在 y 中出现的次数,可以重叠 */ int next[10010]; int KMP_Count(char x[],int m,char y[],int n) {//x 是模式串,y 是主串 int i,j; int ans=0; //preKMP(x,m,next); kmp_pre(x,m,next); i=j=0; while(i<n) { while(-1!=j && y[i]!=x[j]) j=next[j]; i++;j++; if(j>=m) { ans++; j=next[j]; } } return ans; }

    简单例题

    Period

    //注: c++ 中 include <iostream> 不能与 next[] 共存 #include <cstdio> #include <iostream> using namespace std; int Next[1000010]; int n; char p[1000010]; void setNext() { int k=-1; int j=0; Next[0]=-1; while(j<n) { if(k==-1||p[j]==p[k]) { k++;j++; Next[j]=k; }else{ k=Next[k]; } } } int main() { int t=0; while(cin>>n,n) { cin>>p; setNext(); printf("Test case #%d\n",++t); for(int i=1;i<=n;i++) { int len=i-Next[i]; if(i!=len && i%len==0) printf("%d %d\n",i,i/len); } cout<<endl; } }
    最新回复(0)