动物园

Smiling & Weeping

　　　　　　　　　　　　　　　　---- 你是我的，半截的诗，不许别人更改一个字

 

题目链接：P2375 [NOI2014] 动物园 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路详解：这道题目是要求解：有多少个我现在希望求出一个更强大 num 数组一一对于字符串 S 的前 i 个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作num[i]。

  其实，我刚开始是想求解公共最长前后缀再加上跳跃优化~o(╥﹏╥)o这是个错误的思路

　然后，又用s和s的每个后缀的LCP 结合 公共最长前后缀 再加上跳跃优化o(╥﹏╥)o 很可惜TLE

  最后，一想，为什么不能把思路化简一下呢，只求每个(s[0] == s[i])的LCP，仔细想想是不是这样，在这个区间的每个字母都会有这样一个以s[i]为开头的前缀，然后len=min(i , nxt[i])(不能重叠，并且有公共部分),将i~i+len-1部分的num[i]++,思路很清晰，代码也很好实现，(⊙︿⊙) + o(╥﹏╥)o 很可惜TLE ，最后使用 前缀和 和 差分 来小小的优化一波，AC

Talk is cheap , show me the code

#include
using namespace std;
typedef long long ll;
const int mode = 1000000007;
int n , Next[1000100] , slen;
int nxt[1000100] , num[1000100];
ll ans;
char str[1000100];
void getnext(char *s , int slen){
    int p=0 , k=1,l;
    nxt[0] = slen;
    while(p+1 < slen && s[p]==s[p+1]) p++;
    nxt[1] = p;
    for(int i = 2; i < slen; i++){
        p = k+nxt[k]-1;
        l = nxt[i-k];
        if(i+l <= p) nxt[i] = l;
        else {
            int j = max(0 , p-i+1);
            while(i+j < slen && s[i+j] == s[j]) j++;
            nxt[i] = j;
            k = i;
        }
    }
}
void solve(){
    for(int i = 1; i < slen; i++){
        if(str[i] == str[0]){
            int len = min(i , nxt[i]);
            // 会被卡，TLE，改用前缀和，可以通过
            // for(int j = i; j <= i+len-1; j++)
            //     num[i]++;
            num[i]++; num[i+len]--;
        }
    }
    for(int i = 1; i < slen; i++)
        num[i] += num[i-1];
}
int main()
{
    scanf("%d",&n);
    while(n--){
        ans = 1;
        scanf("%s",str);
        slen = strlen(str);
        getnext(str , slen);
        solve();
        for(int i = 1; i < slen; i++)
            ans = ans*(num[i]+1)%mode , num[i] = 0;
        printf("%lld",ans);
        if(n) printf("\n");
    }
    return 0;
}

不要因为也许会改变，就不肯说那句美丽的誓言；

不要因为也许会分离，就不敢求一次倾心的相遇；

文章到此结束，我们下次再见 跳舞(((((ી(･◡･)ʃ)))))