0%

KMP算法

发表于 分类于
本文是在观看了部分KMP算法相关视频后做的笔记

KMP算法适用于字符串匹配，今天通过相关视频，大致了理解了其实现原理以及步骤，学习的视频链接如下（这是未优化版本）：
https://www.bilibili.com/video/av6239731/?p=11
https://www.bilibili.com/video/av3246487?from=search&seid=8682896714663607035
https://study.163.com/course/courseLearn.htm?courseId=468002#/learn/video?lessonId=1023415&courseId=468002
由于我大概理解了原理以及代码实现，所以我到时候后期复习时建议直接看最后一个链接的视频。
我在网上参考了部分其他人使用的C/C++实现的KMP算法实现，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 101


void get_next( int *next,char *a,int la) /*求NEXT[]的值*/
{
   int i=1,j=0 ;
   next[1] = 0 ;
   
   while ( i <= la) /*核心部分*/
   {
      if( a[i] == a[j] || j == 0 )
      {
        j ++ ;
        i ++ ;
        if( a[i] == a[j])
        next[i] = next[j];
        else
        next[i] = j ;
      }
      else
      j = next[j] ;
   }
}

int str_kmp( int *next, char *A ,char *a, int lA,int la)/* EASY*/
{
   int i,j,k ;
   i = 1 ;
   j = 1 ;
   while ( i<=lA && j <= la )
   {
      if(A[i] == a[j] || j == 0 )
      {
          i ++ ;
          j ++ ;
      }
      else
      j = next[j] ;
   }
   
   if ( j> la)
   return i-j+1 ;
   else
   return -1 ;
}

int main(void)
{
  int n,k;
  int next[MAX]={0} ;
  int lA=0,la =0 ;
  char A[MAX],a[MAX] ;
  scanf("%s %s",A,a) ;
  
  lA = strlen(A);
  la = strlen(a);
  for(k=la-1; k>= 0 ;k --)
  a[k+1] = a[k] ;
  for(k=lA-1; k>= 0 ;k --)
  A[k+1] = A[k] ;
  
  get_next(next,a,la) ;
  k = str_kmp(next,A,a,lA,la);
  if ( -1 == k)
  printf("Not Soulation!!! ");
  else
  printf("%d ",k) ;
  system("pause");
  
  return 0 ;
}