首页 > 代码库 > KMP算法

KMP算法

2024-07-14 00:50:12   225人阅读

  • #include <iostream>   
  • #include <cstdlib>   
  • #include <cstdio>   
  • using namespace std;  
  •   
  • //这是整个kmp中最核心的地方   
  • int get_next(const char*t, int *next)  
  • {  
  •     int i = 0;  
  •     int j = -1; //设置j = -1，非常巧妙   
  •     int len = strlen(t);  
  •     memset(next,0, sizeof(int) * len);  
  •     next[0] = -1;  
  •     while(i < len - 1)  
  •     {  
  •         if(j == -1 || t[i] == t[j]) //前面的判断，j == -1, 非常巧妙   
  •         {  
  •             i++;  
  •             j++;  
  •             next[i] = j;    //将后面的next数组元素赋值   
  •         }  
  •         else  
  •             j = next[j];  
  •     }  
  • }  
  •   
  • int kmp(const char *s, const char *t)  
  • {  
  •     int i = 0;  
  •     int j = 0;  
  •     int next[100];  
  •     get_next(t,next);  
  •     while(i < strlen(s) && j < strlen(t))  
  •     {  
  •         if(j == - 1 || s[i] == t[j])    //如果j为-1，或者模式串和主串相等，两者继续往下比较   
  •         {  
  •             i++;  
  •             j++;  
  •         }  
  •         else  
  •             j = next[j];  
  •     }  
  •   
  •     if(j >= (int)strlen(t))  
  •     {  
  •         cout << "found " << endl;  
  •         return 0;  
  •     }  
  •   
  •     cout << "not found" <<endl;  
  •     return 0;  
  • }  


联系
我们