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;   
}

补充：软件开发 , C语言 ,