Problem Description

解法：假设知道了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;

}