字元串hash - POJ 3461 OulipoOulipo Problem's Link

----------------------------------------------------------------------------

Mean: 

給你一個模式串P和一個母串S，讓你統計P串在S串中出現的次數.

analyse:

一開始想到的就是使用KMP，就用KMP寫了，93ms，挺快的.

我又用AC自動機寫了一遍，萬萬沒想到竟然逾時了.

後來看别人有用字元串hash寫的，于是又用字元串hash寫了一遍，代碼30+行，而且速度也挺快，173ms.

字元串hash确實是一個好東西 在字元串hash中又學到了unsigned long long超範圍後會自動對2^64取模，省去了手動取模.

Time complexity: O(N+M)

view code

 1.字元串hash代碼

#include<stdio.h>

#include<string.h>

#define ULL unsigned long long

int seed=100;

char s1[10005],s2[1000005];

int main()

{

   int t;

   scanf("%d",&t);

   while(t--)

   {

       scanf("%s%s",s1,s2);

       int len1=strlen(s1),len2=strlen(s2);

       ULL a1=0,a2=0,l1=1;

       for(int i=0;i<len1;++i)

       {

           a1=a1*seed+(s1[i]-'A'+1);

           l1*=seed;

       }

           a2=a2*seed+(s2[i]-'A'+1);

       int ans=0;

       if(a1==a2) ans++;

       for(int i=len1;i<len2;++i)

           a2=a2*seed+(s2[i]-'A'+1)-l1*(s2[i-len1]-'A'+1);

           if(a2==a1) ans++;

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

   }

   return 0;

}

2.KMP代碼

// Memory   Time

// 1347K     0MS

// by : Snarl_jsb

// 2014-10-04-11.53

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<vector>

#include<queue>

#include<stack>

#include<map>

#include<string>

#include<climits>

#include<cmath>

#define N 1000010

#define LL long long

using namespace std;

vector<int> next;

void GetNext(char s[])

   int len=strlen(s),k=0;

   next.clear();

   next.push_back(0);

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

       while(k!=0&&s[i]!=s[k])

           k=next[k-1];

       if(s[i]==s[k])

           k++;

       next.push_back(k);

int KMP(char s1[],char s2[])

   int l1=strlen(s1),l2=strlen(s2);

   int k=0,ans=0;;

   for(int i=0;i<l2;++i)

       while(k!=0&&s2[i]!=s1[k])

       if(s2[i]==s1[k])

       if(k==l1)

           ans++;

   return ans;

       GetNext(s1);

       printf("%d\n",KMP(s1,s2));

3.AC自動機(TLE)

/**

* -----------------------------------------------------------------

* Copyright (c) 2016 crazyacking.All rights reserved.

*       Author: crazyacking

*       Date  : 2016-01-18-23.59

*/

#include <queue>

#include <cstdio>

#include <set>

#include <string>

#include <stack>

#include <cmath>

#include <climits>

#include <map>

#include <cstdlib>

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

typedef long long(LL);

typedef unsigned long long(ULL);

const double eps(1e-8);

const int N = 1001000;

char str[N];

struct node

   node *next[30];

   node *fail;

   int count;

   node()

       for(int i = 0; i < 30; i++)

           next[i] = NULL;

       count = 0;

       fail = NULL;

}*q[N];

node *root;

int head, tail;

void Insert(char *str)

   node *p = root;

   int i = 0, index;

   while(str[i])

       index = str[i] - 65;

       if(p->next[index] == NULL)

           p->next[index] = new node();

       p = p->next[index];

       i++;

   p->count++;

void build_ac_automation(node *root)

   root->fail = NULL;

   q[tail++] = root;

   while(head < tail)

       node *temp = q[head++];

       node *p = NULL;

           if(temp->next[i] != NULL)

           {

               if(temp == root) temp->next[i]->fail = root;

               else

               {

                   p = temp->fail;

                   while(p != NULL)

                   {

                       if(p->next[i] != NULL)

                       {

                           temp->next[i]->fail = p->next[i];

                           break;

                       }

                       p = p->fail;

                   }

                   if(p == NULL) temp->next[i]->fail = root;

               }

               q[tail++] = temp->next[i];

           }

int total=0;

int Query(node *root)

   int i = 0, cnt = 0, index;

   int idx=0;

       while(p->next[index] == NULL && p != root);

       p = p->fail;

       if(p == NULL)

           p = root;

       node *temp = p;

       while(temp != root && temp->count != -1)

           if(temp->count>0)

               cnt ++;

           temp = temp->fail;

   return cnt;

   cin>>t;

       head=tail=0;

       root=new node();

       scanf("%s",str);

       Insert(str);

       build_ac_automation(root);

//        Query(root);

       printf("%d\n",Query(root));

--------------------------------------------------------- End.

轉載請注明：http://www.cnblogs.com/crazyacking/