ACdream 1116 Gao the string! （扩展KMP+矩阵快速幂）

川长思鸟来 2022-06-09 06:15 302阅读 0赞

题目链接：  
[ACdream 1116][]

题意：  
give you a string, please output the result of the following function mod 1000000007  
∑i=n−1i=0f(a\[i\])  
n is the length of the string。  
f(i) 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\] )  
比如 ：输入：aa，输出：3。  
1.对于aa 这个后缀，前缀 a 出现了两次，前缀 aa 出现了一次，总共三次。  
2.对于 a 这个后缀，前缀 a 出现了一次。  
所以答案是f(3)\+f(1)=1\+2=3。

题解：  
我们用next\[i\]\+1表示 T\[i−n\] 和 T\[1−n\] 的最长公共前缀，那么 a\[i\]=next\[i\]\+next\[i\+1\]......\+next\[n\]。  
求最长公共前缀 (lcp) 有 3 种方法 ： 扩展kmp , hash 和后缀数组 。

AC代码：

#include<cstdio>
    #include<cstring>
    #include<iostream>
    //using namespace std;
    const int mod = 1e9+7;
    struct matrix
    {
        long long factor[2][2];
    }M;
    matrix multi(matrix x,matrix y)
    {
        matrix temp;
        temp.factor[0][0] = (x.factor[0][0] * y.factor[0][0] + x.factor[0][1] * y.factor[1][0]) % 1000000007;
        temp.factor[0][1] = (x.factor[0][0] * y.factor[0][1] + x.factor[0][1] * y.factor[1][1]) % 1000000007;
        temp.factor[1][0] = (x.factor[1][0] * y.factor[0][0] + x.factor[1][1] * y.factor[1][0]) % 1000000007;
        temp.factor[1][1] = (x.factor[1][0] * y.factor[0][1] + x.factor[1][1] * y.factor[1][1]) % 1000000007;
        return temp;
    }
    matrix qpower(int n)
    {
        if(n == 1)return M;
        matrix tmp = qpower(n>>1);
        if(n&1){
            return multi(multi(tmp,tmp),M);
        }
        else return multi(tmp,tmp);
    }
    int fib(int num)
    {
        M.factor[0][0] = 0;
        M.factor[0][1] = 1;
        M.factor[1][0] = 1;
        M.factor[1][1] = 1;
    
        int n = num -1;
        if(n > 0){
            matrix tmp =qpower(n);
            return tmp.factor[1][1];
        }
        else if(n == -1)return 0;
        else if(n == 0) return 1;
    }
    int min(int a,int b)
    {
        return a > b ? b : a; 
    }
    int next[100010];
    
    void ex_kmp(char *t,int len)
    {
        next[0] = len - 1; 
        int j = 0;
        while( 1 + j < len && t[j] == t[1 + j]) j++;
        next[1] =  j - 1;
        int id = 1;
        for(int i = 2;i < len; i++)
        {
            int p = next[id] + id;
            int l = next [i - id];
            if(p < i)next[i] = -1;
            else next[i] = min(l, p - i);
            while(next[i] + i + 1 < len && t[next[i] + i + 1]== t[next[i] + 1]){
                next[i] ++;
            }
            if(i+next[i] > id + next[id]){
                id  = i;
            }
         } 
    }
    char T[100010];
    int main(){
    
        while(~scanf("%s",T))
        {
            int len = strlen(T);
            ex_kmp(T,len);
    
        //  for(int i=0;i<5;i++)std::cout<<next[i]<<" ";std::cout<<std::endl;
    
            int sum = 0,ans = 0;
            for(int i=len-1;i>=0;--i)
            {
                sum += next[i] + 1;
                ans = (ans + fib(sum))%mod;
    
            //  std::cout<<"ans="<<ans<<std::endl; 
            }
            printf("%d\n",ans); 
        }
        return 0;
    }

[ACdream 1116]: http://acdream.info/problem?pid=1116