题解【DHOJ】 Oulipo

· · 个人记录

Oulipo

题目描述 给出两个串s1和s2(只有大写字母)，求S1在S2中出现了多少次？

例如S1="ABA",S2="ABABA"，答案为2.

输入T组数据，对每组数据输出结果。

每组数据保证stlen(S1)<=10000,strlen(S2)<=1000000;

这里主要使用的就是滚动哈希算法，把字符串看作是b进制的数，这样就可以对于每一个字符串体现出不同的数值。

例如说十进制的原理就是这样的

N_{10}=a\times 10^0+ b\times 10^1+ c\times 10^2...

所以换成字符串就应该是这样的

b=26

N_{26}=c_1\times b^0+c_2\times b^1+c_3\times b^2...

所以我们采用的哈希函数就是

设H(C,k)为前k个字符构成的字符串的哈希值，则（以下均不考虑取模的情况）

H(C,k+1)=H(C,k)\times b+c_{k+1}

很明显，这是一个递推的过程（想要计算k+1需要用到k）

那么，以下就是找到子串的判别式

H[C',strlen(C')]==H(C,k+n)-H(C,k)\times b^n

所以，只要预先求出b的n次方，我们就可以在O（1）的时间复杂度内求出子串的哈希值。

但是鉴于这一个哈希值有可能会很大，所以说我们使用了64位无符号整数计算哈希值，用自然溢出省去取模运算。

陷阱

事实上空间复杂度并不需要这么大，老师自己都没有意识到，其实计算b的n次方（其中n是子串的长度），开数组储存b的时候不需要开到strlen(b)那么大，事实上只需要达到strlen(a)就可以了。因为这道题里面的主串的哈希值是递推求解的，并没有用到b。

源代码

#include <cstdio>
#include <cstring>
#define MAX_A 10001
#define MAX_B 1000001
using namespace std;
const int base=27;
int n,len_a,len_b;
char a[MAX_A],b[MAX_B];
unsigned long long power[MAX_A],sum[MAX_B],s;
void setup();
int main()
{
    scanf("%d",&n);
    setup();
    for (int i=1;i<=n;i++)
    {
        scanf(" %s",a+1);
        scanf(" %s",b+1);
        len_a=strlen(a+1);
        len_b=strlen(b+1);
        for (int i=1;i<=len_b;i++)
            sum[i]=sum[i-1]*base+(unsigned long long)(b[i]-'A'+1);
        s=0;
        for (int i=1;i<=len_a;i++)
            s=s*base+(unsigned long long)(a[i]-'A'+1);
        int ans=0;
        for (int i=0;i<=len_b-len_a;i++)
            if (s==sum[i+len_a]-sum[i]*power[len_a])
                ans++;
        printf("%d\n",ans);
    }
}
void setup()
{
    power[0]=1;
    for (int i=1;i<MAX_A;i++)
        power[i]=power[i-1]*base;
}

参考链接

THOJ http://47.104.154.247/problem.php?cid=1015&pid=0

POJ http://poj.org/problem?id=3461