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

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int mode = 1000000007;
 5 int n , Next[1000100] , slen;
 6 int nxt[1000100] , num[1000100];
 7 ll ans;
 8 char str[1000100];
 9 void getnext(char *s , int slen){
10     int p=0 , k=1,l;
11     nxt[0] = slen;
12     while(p+1 < slen && s[p]==s[p+1]) p++;
13     nxt[1] = p;
14     for(int i = 2; i < slen; i++){
15         p = k+nxt[k]-1;
16         l = nxt[i-k];
17         if(i+l <= p) nxt[i] = l;
18         else {
19             int j = max(0 , p-i+1);
20             while(i+j < slen && s[i+j] == s[j]) j++;
21             nxt[i] = j;
22             k = i;
23         }
24     }
25 }
26 void solve(){
27     for(int i = 1; i < slen; i++){
28         if(str[i] == str[0]){
29             int len = min(i , nxt[i]);
30             // 会被卡，TLE，改用前缀和，可以通过
31             // for(int j = i; j <= i+len-1; j++)
32             //     num[i]++;
33             num[i]++; num[i+len]--;
34         }
35     }
36     for(int i = 1; i < slen; i++)
37         num[i] += num[i-1];
38 }
39 int main()
40 {
41     scanf("%d",&n);
42     while(n--){
43         ans = 1;
44         scanf("%s",str);
45         slen = strlen(str);
46         getnext(str , slen);
47         solve();
48         for(int i = 1; i < slen; i++)
49             ans = ans*(num[i]+1)%mode , num[i] = 0;
50         printf("%lld",ans);
51         if(n) printf("\n");
52     }
53     return 0;
54 }

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

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

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