本文主要向大家介绍了 C/C++知识点之KMP，通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。

• kmp
  

  void getnx(string str,int *nx)
  {
  int len=str.length();int i=0,k=-1;nx[0]=-1;
  while(i<len)if(k==-1||str[i]==str[k])nx[++i]=++k;else k=nx[k];
  }
  int index(string str,string p)
  {
  int i=0,j=0;int len1=str.length(),len2=p.length();
  if(len1==1&&len2==1)if(str[0]==p[0])return 0;else return -1;
  int nx[N];getnx(p,nx);
  while(i<len1&&j<len2)
  if(j==-1||str[i]==p[j])i++,j++;else j=nx[j];
  if(j==len2)return i-len2;else return -1;
  }
  int Count(string str,string p)
  {
  int ans=0,i=0,j=0;int nx[N];
  int len1=str.length(),len2=p.length();
  if(len1==1&&len2==1)if(str[0]==p[0])return 1;else return 0;
  getnx(p,nx);
  for(i=0;i<len1;i++)
  {
      while(j>0&&str[i]!=p[j])j=nx[j];
      if(str[i]==p[j])j++;
      if(j==len2)ans++,j=nx[len2];
  }
  return ans;
  }




• exkmp
  

  #include<iostream>
  #include<cstdio>
  #include<cstring>
  #include<algorithm>
  using namespace std;
  const int maxn=50001;
  int nxt[maxn],ex[maxn];
  void GETNEXT(char *str)
  {
  int i=0,j,po,len=strlen(str);
  nxt[0]=len;
  while(str[i]==str[i+1]&&i+1<len)
  i++;
  nxt[1]=i;
  po=1;
  for(i=2;i<len;i++)
  {
      if(nxt[i-po]+i<nxt[po]+po)
      nxt[i]=nxt[i-po];
      else
      {
          j=nxt[po]+po-i;
          if(j<0)j=0;
          while(i+j<len&&str[j]==str[j+i])
          j++;
          nxt[i]=j;
          po=i;
      }
  }
  }
  void EXKMP(char *s1,char *s2)
  {
  int i=0,j,po,len=strlen(s1),l2=strlen(s2);
  GETNEXT(s2);
  while(s1[i]==s2[i]&&i<l2&&i<len)
  i++;
  ex[0]=i;
  po=0;
  for(i=1;i<len;i++)
  {
      if(nxt[i-po]+i<ex[po]+po)
      ex[i]=nxt[i-po];
      else
      {
          j=ex[po]+po-i;
          if(j<0)j=0;
          while(i+j<len&&j<l2&&s1[j+i]==s2[j])
          j++;
          ex[i]=j;
          po=i;
      }
  }
  }

本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C/C+频道！