HDU 1686 Oulipo

題意：求模式串在主串中出現的次數【可重疊】

Sample Input
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

Sample Output
1
3
0

對代碼中神奇的地方進行解釋：

那麼3的意義可以表示為 
 
可見next[len2]的意義：前綴和後綴的最長匹配長度

現在就以這個為模式串模擬一下：
主串：    A B A B A B C A B A B A A B 
 
模式串：A B A B C A B A

匹配成功後下一步的情況應為：
主串：    A B A B A B C A B A B A A B 
 
模式串：                                A B A B C A B A
指針直接移動到紅色部分進行匹配

如何理解呢？
我們先不看最後那2個字符A和B，就可以發現最大前綴【指前綴和後綴的最長匹配長度】直接挪動到最大後綴那裡了，為什麼可以這樣呢？因為前面都是顯然不能夠匹配成功的
可以向前移動一位試試看：
主串：    A B A B A B C A B A B A A B 
 
模式串：                            A B A B C A B A
我們先不看最後那2個字符A和B，可以看到現在是4長度的前綴與4長度的後綴比較，顯然不
可匹配，因為最大匹配長度是3【指前綴和後綴的最長匹配長度】，顯然再向前移也不行的

第一次長篇大論，若有錯誤或不明白之處，請指出
C++代碼 
#include <iostream>  
#include <fstream>  
#include <algorithm>  
#include <string>  
#include <set>  
//#include <map>  
#include <queue>  
#include <utility>  
#include <stack>  
#include <list>  
#include <vector>  
#include <cstdio>  
#include <cstdlib>  
#include <cstring>  
#include <cmath>  
#include <ctime>  
#include <ctype.h>  
using namespace std;  
#define L1 1000005  
#define L2 10005  
 
int len1, len2, next[L2], res;  
char s[L1], p[L2];  
 
void get_next ()  
{  
    int k = -1, j = 0;  
    next[0] = -1;  
    while (j < len2)    //這裡必須要推導出next[len2]  
    {  
        if (k == -1 || p[k] == p[j])  
        {  
            j++, k++;  
            if (p[k] != p[j])  
                next[j] = k;  
            else next[j] = next[k];  
        }  
        else k = next[k];  
    }  
    /*for (j = 0; j <= len2; j++) 
        cout << next[j] << ; 
    cout << endl;*/ 
}  
void kmp ()  
{  
    int i = 0, j = 0;  
    while (i < len1 && j < len2)  
    {  
        if (j == -1 || s[i] == p[j])  
            i++, j++;  
        else j = next[j];  
        if (j >= len2)      
            res++, j = next[j];    //灰常神奇的地方，用到next[len2]，效率大大提高  
    }  
}  
int main()  
{  
    int t;  
    scanf ("%d", &t);  
    while (t--)  
    {  
        scanf ("%s%s", p, s);  
        len1 = strlen(s);  
        len2 = strlen(p);  
        res = 0;  
        get_next();  
        kmp ();  
        printf ("%d ", res);  
    }  
    return 0;  
}