首页 > 代码库 > Acdreamoj1116（Gao the string!）字符串hash+二分+矩阵快速幂

Acdreamoj1116（Gao the string!）字符串hash+二分+矩阵快速幂

2024-07-08 05:24:18   218人阅读

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] )

解法：如果知道了num[i]表示i开始的后缀s[i....n]跟前缀s[1...]之间的公共的前缀，那么以i开头的后缀中就匹配了num[i]个前缀了

所以i这个后缀出现的前缀的数量实际上就是num[i] + num[i+1] + .. num[n]. 求出来之后快速幂求斐波那契数列相应项大小即可。求lcp的时候是二分+hash；字符串hash中，seed为31（java库源码中是这个数，应该是效果比较好的） 

代码：

/******************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string.h>
//freopen ("in.txt" , "r" , stdin);
using namespace std;

#define eps 1e-8
#define zero(_) (abs(_)<=eps)
const double pi=acos(-1.0);
typedef long long LL;
const int Max=100010;
const int INF=1000000007;
const int hashseed=31;

LL seed[Max];
LL has[Max];
char s[Max];
LL num[Max];
int len=0;
struct matrix
{
    LL num[2][2];
    matrix()
    {
        memset(num,0,sizeof num);
    }
};
matrix operator*(const matrix& a,const matrix& b)
{
    matrix ans;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
        for(int k=0;k<2;k++)
        ans.num[j][k]+=(a.num[j][i]*b.num[i][k])%INF;
    return ans;
}
matrix operator^(matrix a,LL n)
{
    matrix ans;
    ans.num[0][0]=1;
    ans.num[1][1]=1;
    while(n)
    {
        if(n&1)
        {
            ans=ans*a;
        }
        a=a*a;
        n>>=1;
    }
    return ans;
}
LL getans(LL t)
{
    if(t==0)
        return 0;
    if(t<=2)
        return 1;
    matrix tool;
    tool.num[0][0]=1;
    tool.num[0][1]=1;
    tool.num[1][0]=1;
    tool=tool^(t-1);
    return tool.num[0][0]%INF;
}
void init()
{
    seed[0]=1;
    for(int i=1; i<Max; i++)
        seed[i]=(seed[i-1]*hashseed)%INF;
}
LL Hash(int i,int L)
{
    return ((has[i]-has[i+L]*seed[L])%INF+INF)%INF;
}
bool OK(int i,int l)
{
    return Hash(0,l)==Hash(i,l);
}
void getnum(int i)
{
    int left=i,right=len-1;
    while(left<=right)
    {
        int middle=(left+right)/2;
        if(OK(i,middle-i+1))
            left=middle+1;
        else
            right=middle-1;
    }
    num[i]=right-i+1;
}
void makehash()
{
    for(int i=len-1;i>=0;i--)
    {
        has[i]=(has[i+1]*hashseed+s[i])%INF;
    }
    num[0]=len;
    for(int i=1;i<len;i++)
    {
        getnum(i);
    }
}
int main()
{
    init();
   while(scanf("%s",s)==1)
   {
       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<<'\n';
   }
    return 0;
}



联系
我们