做网站主要用哪种语言,网站排名推广自己怎么做,wordpress做图片集,做网站业务的怎么找资源Description 近日#xff0c;园长发现动物园中好吃懒做的动物越来越多了。例如企鹅#xff0c;只会卖萌向游客要吃的。为了整治动物园的不良风气#xff0c;让动物们凭自己的真才实学向游客要吃的#xff0c;园长决定开设算法班#xff0c;让动物们学习算法。 某天#x…Description 近日园长发现动物园中好吃懒做的动物越来越多了。例如企鹅只会卖萌向游客要吃的。为了整治动物园的不良风气让动物们凭自己的真才实学向游客要吃的园长决定开设算法班让动物们学习算法。 某天园长给动物们讲解KMP算法。 园长“对于一个字符串S它的长度为L。我们可以在O(L)的时间内求出一个名为next的数组。有谁预习了next数组的含义吗” 熊猫“对于字符串S的前i个字符构成的子串既是它的后缀又是它的前缀的字符串中它本身除外最长的长度记作next[i]。” 园长“非常好那你能举个例子吗” 熊猫“例S为abcababc则next[5]2。因为S的前5个字符为abcabab既是它的后缀又是它的前缀并且找不到一个更长的字符串满足这个性质。同理还可得出next[1] next[2] next[3] 0next[4] next[6] 1next[7] 2next[8] 3。” 园长表扬了认真预习的熊猫同学。随后他详细讲解了如何在O(L)的时间内求出next数组。 下课前园长提出了一个问题“KMP算法只能求出next数组。我现在希望求出一个更强大num数组一一对于字符串S的前i个字符构成的子串既是它的后缀同时又是它的前缀并且该后缀与该前缀不重叠将这种字符串的数量记作num[i]。例如S为aaaaa则num[4] 2。这是因为S的前4个字符为aaaa其中a和aa都满足性质‘既是后缀又是前缀’同时保证这个后缀与这个前缀不重叠。而aaa虽然满足性质‘既是后缀又是前缀’但遗憾的是这个后缀与这个前缀重叠了所以不能计算在内。同理num[1] 0,num[2] num[3] 1,num[5] 2。” 最后园长给出了奖励条件第一个做对的同学奖励巧克力一盒。听了这句话睡了一节课的企鹅立刻就醒过来了但企鹅并不会做这道题于是向参观动物园的你寻求帮助。你能否帮助企鹅写一个程序求出num数组呢 特别地为了避免大量的输出你不需要输出num[i]分别是多少你只需要输出对1,000,000,007取模的结果即可。 Input 第1行仅包含一个正整数n 表示测试数据的组数。随后n行每行描述一组测试数据。每组测试数据仅含有一个字符串SS的定义详见题目描述。数据保证S 中仅含小写字母。输入文件中不会包含多余的空行行末不会存在多余的空格。 Output 包含 n 行每行描述一组测试数据的答案答案的顺序应与输入数据的顺序保持一致。对于每组测试数据仅需要输出一个整数表示这组测试数据的答案对 1,000,000,007 取模的结果。输出文件中不应包含多余的空行。 Sample Input 3 aaaaa ab abcababc Sample Output 36 1 32 HINT n≤5,L≤1,000,000 将KMP算法中的next[i]向i连一条边得到KMP树。 那么num[i]其实就是i沿KMP树向上第一个长度i/2的节点在KMP树上的深度。 那么我们在KMP的时候再维护一下那个节点就行了。 #includecstdio
#includecctype
#includequeue
#includecmath
#includecstring
#includealgorithm
#define rep(i,s,t) for(int is;it;i)
#define dwn(i,s,t) for(int is;it;i--)
#define ren for(int ifirst[x];i;inext[i])
using namespace std;
inline int read() {int x0,f1;char cgetchar();for(;!isdigit(c);cgetchar()) if(c-) f-1;for(;isdigit(c);cgetchar()) xx*10c-0;return x*f;
}
const int maxn1000010;
const int mod1000000007;
char s[maxn];
int f[maxn],dep[maxn];
int main() {dwn(T,read(),1) {scanf(%s,s);int nstrlen(s);f[1]f[0]0;dep[1]1;int j0,j20;long long ans1;rep(i,1,n-1) {while(js[i]!s[j]) jf[j];if(s[i]s[j]) j;f[i1]j;dep[i1]dep[j]1;while(j2s[i]!s[j2]) j2f[j2];if(s[i]s[j2]) j2;while(j2i11) j2f[j2];(ans*dep[j2]1)%mod;}printf(%lld\n,ans);}return 0;
} View Code 转载于:https://www.cnblogs.com/wzj-is-a-juruo/p/5051676.html
