KMP_Algorithm.rar

  • PUDN用户
    了解作者
  • Visual C++
    开发工具
  • 98KB
    文件大小
  • rar
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 3
    下载次数
  • 2012-08-27 15:47
    上传日期
KMP算法 字符串匹配算法 c++源码实现 方便快捷 算法清晰
KMP_Algorithm.rar
  • KMP_Algorithm
  • Debug
  • KMP_Algorithm.pdb
    433KB
  • KMP_Algorithm.obj
    6.9KB
  • vc60.pdb
    52KB
  • KMP_Algorithm.exe
    172.1KB
  • KMP_Algorithm.dsw
    551B
  • KMP_Algorithm.cpp
    1.9KB
  • KMP_Algorithm.ncb
    41KB
  • KMP_Algorithm.opt
    52.5KB
  • KMP_Algorithm.dsp
    4.3KB
  • KMP_Algorithm.plg
    1.2KB
内容介绍
#include "stdio.h" #include "string.h" #define STOP "quit" #define GINGALS "/n*******************************/n" // int KMPIndex(const char *T,const char *P,int pos); void getNext(const char *P,int next[]); int KMPIndexHelp(const char *T,const char *P,int pos,int next[]); int main(void) { char pattern_str[1001]; char target_str[1001]; int position; printf("\nenter the target str :(exit with quit)\n"); gets(target_str); //putchar('\n'); //puts(pattern_str); printf("\nenter the pattern str:(exit with quit)\n"); gets(pattern_str); //putchar('\n'); //puts(target_str); while ((strcmp(pattern_str,STOP))&&(strcmp(target_str,STOP))) { printf("\nthe target str is: %s\n ",target_str); printf("\nthe pattern str is: %s\n ",pattern_str); position=KMPIndex(target_str,pattern_str,0); printf("\nthe position of pattern str in the target str is: %d\n",position); printf("\nenter the target str :(exit with quit)\n"); gets(target_str); printf("\nenter the pattern str:(exit with quit)\n"); gets(pattern_str); } return 1; } int KMPIndex(const char *T,const char *P,int pos) { int *next=new int[strlen(P)]; getNext(P,next); int result=KMPIndexHelp(T,P,pos,next); printf("\n%s\n",GINGALS); delete []next; return result; } void getNext(const char *P,int next[]) { next[0]=-1; int j=0,k=-1; while(j<(strlen(P)-1)) { if(k==-1) { next[j+1]=0; j=1;k=0; } else if(P[k]==P[j]) { next[j+1]=k+1; j++;k++; } else { k=next[k]; } } for (int m=0;m<strlen(P);m++) { printf(" %d ",next[m]); } } int KMPIndexHelp(const char *T,const char *P,int pos,int next[]) { int i=pos,j=0; while ((i<strlen(T))&&(j<strlen(P))) { if(j==-1) { i++;j=0; } else if (P[j]==P[i]) { i++;j++; } else { j=next[j]; } } if(j<strlen(P)) return -1; else return i-j; }
评论
    相关推荐