KMP算法

連結真的寫得很詳細，還有範例補助說明
https://www.ptt.cc/bbs/b99902HW/M.1300796484.A.EE1.html

p.s. 一定要先看完上文才會懂此篇喔(此篇只是補充)

設：原字串(org), 比較字串(pat)
看完上面那篇再補充一下一些我當初讀完碰到的盲點
1. 我們發現F(X)使用起來很方便，但為什麼可以這樣用呢？
F(X)的意義其實就是在找一個 "存在的長度 k ，使的比較字串[1, i-k]和 [k, i-1]這兩段相同的情況"(也就是此段跟前綴字串相同)
但為什麼利用F(X)對應到原字串比較時會產生這種優勢？是因為前綴字已做過比對與原字串相同，不用在比一次了(相當於 pat[k, i-1]=pat[1, i-k])

ababacbababab
ababab

ababacbababab
    ababab

AC code: (http://hihocoder.com/contest/hiho3/problem/1)

 1  #include <stdio.h>

 2  #include <string.h>

 3  #include <iostream>

 4  using namespace std;

 5  char W[10010], T[1000010];

 6  int wlen, tlen;

 7  int next[10010];

 8  void getNext()

 9  {

10      int j, k;

11      j = 0;

12      k = -1;

13      next[0] = -1;

14      while (j < wlen)

15      {

16          if (k == -1 || W[j] == W[k])

17          {

18              next[++j] = ++k;

19          }

20          else k = next[k];

21      }

22  }

23  int KMP_count()

24  {

25      int ans = 0;

26      int i, j = 0;

27      if (wlen == 1 && tlen == 1) //only one element

28      {

29          if (W[0] == T[0])return 1;

30          else return 0;

31      }

32      getNext(); 

33      for (i = 0; i < tlen; i++)

34      {

35          while (j > 0 && T[i] != W[j]) //比對發現不同

36              j = next[j];

37          if (W[j] == T[i])j++; //比對相同

38          if (j == wlen) //找到一組相同字串

39          {

40              ans++;

41              j = next[j];

42          }

43      }

44      return ans;

45  }

46  int main()

47  {

50      int tcase;

51      scanf("%d", &tcase);

52      while (tcase--)

53      {

54          scanf("%s%s", W, T);

55          wlen = strlen(W);

56          tlen = strlen(T);

57 

58          printf("%d\n", KMP_count());

59      }

60      return 0;

61  }