hdu1686 KMP裸題
秋招快有著落啦，十一月中去北京區賽膜拜眾神。
哎，好長一段時間沒有刷過，重頭拾起，最近得專題是字符串。
Trie前一排又敲了一遍，KMP今天敲了一下。
題目一大堆廢話，實際就是判斷模式串出現得次數，我是對著算法導論偽代碼敲得，一次AC，真得很水。
/***********************************************************
> OS : Linux 3.13.0-24-generic (Mint-17)
> Author : yaolong
> Mail : [email protected]
> Time : 2014年09月24日 星期三 15時31分51秒
**********************************************************/
#include
#include
#include
#include
using namespace std;
int next[12345];
char p[12345];
char T[1234567];
void build_next ( int m )
{
next[1] = 0;
int k = 0;
for ( int q = 2; q <= m; q++ )
{
while ( k > 0 && p[k + 1] != p[q] )
{
k = next[k];
}
if ( p[k + 1] == p[q] )
{
k = k + 1;
}
next[q] = k;
}
}
int kmp ( int n, int m )
{
build_next ( m );
int q = 0;
int res = 0;
for ( int i = 1; i <= n; i++ )
{
while ( q > 0 && p[q + 1] != T[i] )
{
q = next[q];
}
if ( p[q + 1] == T[i] )
{
q = q + 1;
}
if ( q == m )
{
//cout << "Here" << i-m<<"q";
++res;
q = next[q];
//cout<
