字符串hash - POJ 3461 Oulipo

简介: Oulipo  Problem's Link ---------------------------------------------------------------------------- Mean:  给你一个模式串P和一个母串S,让你统计P串在S串中出现的次数.

Oulipo 

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;
        }
        for( int i = 0; i < len1; ++ i)
        {
            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;
char s1 [ 10005 ], s2 [ 1000005 ];
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 ])
            k = next [ k - 1 ];
        if( s2 [ i ] == s1 [ k ])
            k ++;
        if( k == l1)
        {
            ans ++;
            k = next [ k - 1 ];
        }
    }
    return ans;
}
int main()
{
    int t;
    scanf( "%d" , & t);
    while( t --)
    {
        scanf( "%s%s" , s1 , s2);
        int len1 = strlen( s1 ), len2 = strlen( s2);
        GetNext( s1);
        printf( "%d \n " , KMP( s1 , s2));
    }
    return 0;
}

 

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>
using namespace std;
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;
        for( int i = 0; i < 30; i ++)
        {
            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;
    node *p = root;
    int idx = 0;
    while( str [ i ])
    {
        index = str [ i ] - 65;
        while(p -> next [ index ] == NULL && p != root);
       p = p -> fail;
       p = p -> next [ index ];
        if(p == NULL)
           p = root;
        node * temp = p;
        while( temp != root && temp -> count != - 1)
        {
            if( temp -> count > 0)
            {
                cnt ++;
            }
            temp = temp -> fail;
        }
        i ++;
    }
    return cnt;
}

int main()
{
    int t;
    cin >> t;
    while( t --)
    {
        head = tail = 0;
        root = new node();
        scanf( "%s" , str);
        Insert( str);
        build_ac_automation( root);
        scanf( "%s" , str);
//        Query(root);
        printf( "%d \n " , Query( root));
    }
    return 0;
}

 

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

转载请注明:http://www.cnblogs.com/crazyacking/

目录
相关文章
|
6月前
|
Java
HDU-1686-Oulipo
HDU-1686-Oulipo
24 0
|
6月前
洛谷P1204 or SSL-1088 USACO 1.2 挤牛奶
洛谷P1204 or SSL-1088 USACO 1.2 挤牛奶
hdu 2502 月之数
hdu 2502 月之数
29 0
|
算法
山东第一届省赛 Greatest Number(优雅暴力+二分)
山东第一届省赛 Greatest Number(优雅暴力+二分)
69 1
[SDUT 2414] | 山东省第三届省赛 An interesting game | 最小费用最大流
题目描述 Xiao Ming recently designs a little game, in front of player there are N small hillsides put in order, now Xiao Ming wants to increase some hillsides to block the player, so he prepared another M hillsides, but he does not hope it will be too difficult,
164 0
[SDUT 2414] | 山东省第三届省赛 An interesting game | 最小费用最大流
hdu 2094 产生冠军
hdu 2094 产生冠军
145 0
|
算法
HDU - 2063: 过山车
HDU - 2063: 过山车
143 0
|
人工智能 BI
洛谷 P3183 BZOJ 4562 [HAOI2016]食物链
题目描述 如图所示为某生态系统的食物网示意图,据图回答第1小题现在给你n个物种和m条能量流动关系,求其中的食物链条数。物种的名称为从1到n编号M条能量流动关系形如a1 b1a2 b2a3 b3......am-1 bm-1am bm其中ai bi表示能量从物种ai流向物种bi,注意单独的一种孤立生物不算一条食物链 输入输出格式 输入格式:   第一行两个整数n和m,接下来m行每行两个整数ai bi描述m条能量流动关系。
1041 0