HDU 4821 String（2013长春现场赛I题）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4821

字符串题。

现场使用字符串HASH乱搞的。

枚举开头！

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <algorithm>

 #include <queue>

 #include <map>

 #include <set>

 #include <vector>

 #include <string>

 #include <math.h>

 using namespace std;

 int HASH;

 const int MAXN = ;

 int now ;

 struct HASHMAP

 {

     int head[],next[MAXN],size;

     unsigned long long state[MAXN];

     int f[MAXN];

     void init()

     {

         size = ;

         for(int i = ;i < HASH ;i++)

             head[i] = -;

         //memset(head,-1,sizeof(head));

     }

     int insert(unsigned long long val,int _id)

     {

         int h = val % HASH;

         for(int i = head[h];i != -;i = next[i])

         {

             if(val == state[i])

             {

                 int tmp = f[i];

                 f[i] = _id;

                 return tmp;

             }

         }

         f[size] = _id;

         state[size] = val;

         next[size] = head[h];

         head[h] = size++;

         return ;

     }

 }H;

 const int SEED = ;

 unsigned long long P[MAXN];

 unsigned long long S[MAXN];

 unsigned long long a[MAXN];

 char str[MAXN];

 int main()

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     P[] = ;

     for(int i = ;i < MAXN;i++)

         P[i] = P[i-]*SEED;

     int M,L;

     now = -;

     while(scanf("%d%d",&M,&L) == )

     {

         now --;

         scanf("%s",str);

         int n = strlen(str);

         S[] = ;

         for(int i = ;i <= n;i++)

             S[i] = S[i-]*SEED + str[i-];

         int ans = ;

         if(L>= )

             HASH = ;

         else

             HASH = ;

         for(int st = ;st <= L;st++)

         {

             H.init();

             int tmp = ;

             int cnt = ;

             for(int i = st; i + L -  <= n;i += L)

                 a[++cnt] = S[i+L - ] - S[i-] * P[L];

             /*

             for(int i = 1;i <= cnt;i++)

                 cout<<a[i]<<" ";

             cout<<endl;

             */

             for(int i = ;i <= cnt;i++)

             {

                 int l = H.insert(a[i],i);

                 if(i - l >= M)continue;

                 ans += max(, i - M - tmp + );

                 tmp = max(tmp,l + );

                 //printf("%d %d\n",tmp,l);

             }

             ans += max(,cnt+ - M - tmp+);

         }

         printf("%d\n",ans);

     }

     return ;

 }

 /*

 1

 17239715954 17239715954 17417444844 17239715954

 1 0

 2 1

 3 2

 2

 17417444844 17417444845 17595133743

 1 0

 1 0

 3

 17595133744 17595147076 17239702622

 1 0

 1 0

 0

 */