It is well known that AekdyCoin is good at string problems as well as number theory problems. When given a string s, we can write down all the non-empty prefixes of this string. For example:
s: "abab"
The prefixes are: "a", "ab", "aba", "abab"
For each prefix, we can count the times it matches in s. So we can see that prefix "a" matches twice, "ab" matches twice too, "aba" matches once, and "abab" matches once. Now you are asked to calculate the sum of the match times for all the prefixes. For "abab",
it is 2 + 2 + 1 + 1 = 6.
The answer may be very large, so output the answer mod 10007.
The first line is a single integer T, indicating the number of test cases.
For each case, the first line is an integer n (1 <= n <= 200000), which is the length of string s. A line follows giving the string s. The characters in the strings are all lower-case letters.
For each case, output only one number: the sum of the match times for all the prefixes of s mod 10007.
14abab
sample output
6
/*本题题意可以理解为 把串a的各个子串分别作为模式串 查找模式串在主串中出现的次数
我们可以把串a的next函数打印出来 然后对应子串的next也就是next函数中的一部分
所以就不用一个一个子串的去求子串的next函数了
另外 我们可以发现当某个子串只在a中出现一次的时候 再往子串上加字符 即下个子串也一定是1
如aabcde aabc在主串中出现一次 那aabcd肯定更加是1次
所以之后的全是1 就没必要继续调用KMP了 就可以节省很多时间 防止超时
*/
#include<stdio.h>
#include<string.h>
char a[200005];
char b[200005];
int next[200005],d,d2,cnt;
void get_next()
{
int i=1,j=0;
next[1]=0;
while(i<=d)
{
if(j==0||a[i]==a[j]) {i++;j++;next[i]=j;}
else j=next[j];
}
}
int KMP(char *str)
{
int i=1,j=1;
while(i<=d)
{
if(j==0||b[j]==a[i])
{
i++;j++;
if(j==d2+1) {cnt++; j=1;}
}
else j=next[j];
}
return cnt;
}
int main()
{
int t,i,ans,k;
scanf("%d",&t);
while(t--)
{
ans=0;
scanf("%d",&d);
getchar();
gets(a+1);
get_next();
// for(i=1;i<=d;i++)
// printf("%d ",next[i+1]-1);
// printf("\n");
d2=0;
for(i=1;i<=d;i++)
{
cnt=0;
b[i]=a[i];
b[i+1]='\0';
d2++;
k=KMP(&b[1]);
// printf("%d ",k);
if(ans>10007) ans=ans%10007;
else
ans=ans+k;
if(k==1)
{
ans=(ans+(d-i))%10007;
break;
}
}
printf("%d\n",ans);
}
return 0;
}
相关推荐
杭电hdu acm资料所用杭电的acm题
杭电acm解题报告 详细解析2000-2099 适合acm初学者
杭电ACMhdu1163
压缩包包含十份报告,已经通过验收,实验内容:交换机、生成树、静态路由、NAT等完全根据教材实验要求
hdu os lesson=============linux kernel 4.13.11
acm代码,关键使用了strcmp函数以及结构体
杭电ACM课件,与感兴趣的同学分享,内容比较简单,适合初学者。
文件系统 杭电操作系统文件管理系统
杭州电子科技大学ACM培训课件 来自杭电ACM官方论坛 拿来和大家分享一下 想到有些朋友论坛积分不够 现在特地拿来免费供大家下载 希望对ACM初学者能够有所帮助
hdu杭电网络编程结课报告 聊天室
包含实验内容:对应实验要求上的1/2/3/5实验,分别为setName/setNice,petree输出进程,模拟shell,进程通信,文件系统。包含全部实验源代码和详尽的word实验报告。同时包含在线PTA编程题目:进程模拟,模拟进程调度...
杭电OJ部分答案,可以很简单的解决a+b求和问题及其他问题。
杭电ACM1005题源代码,AC了的程序,无问题……
这是老师给我的哦,里面有完整版的HDU杭电ACM课件,还附有2000-2099的解题报告跟DP背包问题,如果你是acm的初学者,那么这是必须的,看了会有很大的帮助哦!
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
利用vjudge源码改造爬虫抓取vjudge全局共享答案资源。 ACMer,请用于参考思路,对拍代码,不要直接提交。
hdu杭电所有题目按照ac数量排序,python分析
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了
2016杭电软工导论期末原题,2018年有三道原题,目测可以用到2020左右,改错题2018原题,2018没有选择题
杭电acm培训课件 杭电acm培训课件 杭电acm培训课件 杭电acm培训课件