首页 > 代码库 > ACdreamOJ 1116 斐波那契数列+hash计算后缀

ACdreamOJ 1116 斐波那契数列+hash计算后缀

2024-08-10 04:15:59   221人阅读

http://acdream.info/problem?pid=1116

Problem Description

give you a string, please output the result of the following function mod 1000000007

技术分享

n is the length of the string

f() is the function of fibonacci, f(0) = 0, f(1) = 1...

a[i] is the total number of times any prefix appear in the suffix s[i....n-1].

(the prefix means s[0...i] )

Input

multiple test cases.

each test case will give you a string consists of lowercase letters, the length of which is no more than 100000.

Output

ouput a number.

Sample Input

aa

Sample Output

3

Hint

样例解释如下：

对于

aa这个后缀，前缀a出现了两次，前缀aa出现了一次，总共三次

对于a这个后缀，前缀a出现了一次

所以答案是f(3) + f(1)

哈希的讲解：刘汝佳大白书P224.基于哈希值的LCP算法

/**
ACdreamOJ 1116 （hash 斐波那契数列+hash）
题目大意：
        求f(num[i])(i:0~len-1)的和。num[i]表示所有的前缀在以i为起点的后缀中出现的次数。
解题思路：
        如果已知num[i],那么利用矩阵连乘就可以求出f(num[i])，因此本题的关键是求出num[i].
        利用hash算法，用has[i]表示以i开头的后缀的哈希值;(hash(i,L)=has(i)-has(i+L)*Hash[L]):表示字符串s[i]~s[i+L]的哈希值.
        利用二分求出num1[i](以i为起点的后缀的字符串和原字符串公共前缀的数目)进而num1[]的后缀和就是num[].
*/
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long LL;
const int seed=31;
const int maxn=100010;
///============== 斐波那契数列求法=============
const int INF=1e9+7;
const int MAX=2;
struct Matrix
{
    LL m[MAX][MAX];
};
Matrix P= {0,1,1,1};
Matrix I= {1,0,0,1};
Matrix matrixmul(Matrix a,Matrix b)//、矩阵相乘
{
    Matrix c;
    for(int i=0; i<MAX; i++)
    {
        for(int j=0; j<MAX; j++)
        {
            c.m[i][j]=0;
            for(int k=0; k<MAX; k++)
                c.m[i][j]+=(a.m[i][k]*b.m[k][j])%INF;
            c.m[i][j]%=INF;
        }
    }
    return c;
}
Matrix quickpow(LL n)///矩阵快速幂
{
    Matrix m=P,b=I;
    while(n)
    {
        if(n&1)
            b=matrixmul(b,m);
        n>>=1;
        m=matrixmul(m,m);
    }
    return b;
}
LL getans(LL t)///返回f(t)的值
{
    if(t==0)
        return 0;
    if(t<2)
        return 1;
    Matrix A=quickpow(t-1);
    return A.m[0][0]+A.m[0][1];
}
///=========================================

///=============字符串后缀哈希值的计算======
LL Hash[maxn],has[maxn],num[maxn];
int len;
char s[maxn];

void init()///初始化
{
    Hash[0]=1;
    for(int i=1; i<maxn; i++)
        Hash[i]=Hash[i-1]*seed;
}

LL get_hash(int i,int L)///得到以i为起点长度为L的后缀的哈希值
{
    return has[i]-has[i+L]*Hash[L];
}

bool ok(int i,int l)
{
    return get_hash(0,l)==get_hash(i,l);
}

void getnum(int i)///二分，求以i为起点的后缀的字符串和原字符串公共前缀的数目
{
    int left=i,right=len-1;
    while(left<=right)
    {
        int mid=(left+right)/2;
        if(ok(i,mid-i+1))
            left=mid+1;
        else
            right=mid-1;
    }
    num[i]=right-i+1;
}

void makehash()///得到每个后缀的哈希值
{
    for(int i=len-1; i>=0; i--)
    {
        has[i]=has[i+1]*seed+s[i];
    }
    num[0]=len;
    for(int i=1; i<len; i++)
        getnum(i);
}

///===========================================

int main()
{
    init();
    
    /* int n;
    while(~scanf("%d",&n))
    cout << getans(n)<< endl;*/
    
    while(~scanf("%s",s))
    {
        memset(has,0,sizeof(has));
        len=strlen(s);
        makehash();
        for(int i=len-1; i>=0; i--)
            num[i]+=num[i+1];
        LL ans=0;
        for(int i=0; i<len; i++)
            ans=(ans+getans(num[i]))%INF;
        cout << ans << endl;
    }
    return 0;
}



ACdreamOJ 1116 斐波那契数列+hash计算后缀


联系
我们