hdu 3336 Count the string
Description
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.
adfsa
Input
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.
Output
For each case, output only one number: the sum of the match times for all the prefixes of s mod 10007.
Sample Input
1
4
abab
Sample Output
6
简单题。
kmp的next数组存的是以当前字符为结尾的且与整个字符串某个前缀匹配的最长后缀。
所以这道题考察的是对next数组的理解。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int mod = 10007;
int jump[200002];
void PrintJump(char *str)
{
jump[0] = -1;
jump[1] = 0;
int len = strlen(str+1);
int j=1,k;
while(j<len) //计算jump[j+1]
{
k = jump[j]; //已知jump[j]==k
while(k!=-1&&str[k+1]!=str[j+1]) k = jump[k];
jump[j+1] = k+1;
j++;
}
}
char str2[200002];
int ans[200002];
int main()
{
int t,len;
scanf("%d",&t);
while(t--)
{
scanf("%d%s",&len,str2+1);
int sum=len%mod;
memset(ans,0,sizeof(ans));
ans[0]=-1;
PrintJump(str2);
for(int i=1;i<=len;i++) {
ans[i]=ans[jump[i]]+1;
while(ans[i]>=mod) ans[i]-=mod;
sum+=ans[i];
while(sum>=mod) sum-=mod;
}
printf("%d\n",sum%mod);
}
}
类似的水题：hdu 4763 Theme Section
| Description It's time for music! A lot of popular musicians are invited to join us in the music festival. Each of them will play one of their representative songs. To make the programs more interesting and challenging, the hosts are going to add some constraints to the rhythm of the songs, i.e., each song is required to have a 'theme section'. The theme section shall be played at the beginning, the middle, and the end of each song. More specifically, given a theme section E, the song will be in the format of 'EAEBE', where section A and section B could have arbitrary number of notes. Note that there are 26 types of notes, denoted by lower case letters 'a' - 'z'. Input The integer N in the first line denotes the total number of songs in the festival. Each of the following N lines consists of one string, indicating the notes of the i-th (1 <= i <= N) song. The length of the string will not exceed 10^6. Output There will be N lines in the output, where the i-th line denotes the maximum possible length of the theme section of the i-th song. Sample Input
Sample Output
|
很水的题，啥都不说，直接上代码。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXN=1000003;
int jump[MAXN];
void PrintJump(char *str)
{
jump[0] = -1;
jump[1] = 0;
int len = strlen(str+1);
int j=1,k;
while(j<len) //计算jump[j+1]
{
k = jump[j]; //已知jump[j]==k
while(k!=-1&&str[k+1]!=str[j+1]) k = jump[k];
jump[j+1] = k+1;
j++;
}
}
char str2[MAXN];
int main()
{
int t,len;
scanf("%d",&t);
while(t--)
{
scanf("%s",str2+1);
len = strlen(str2+1);
PrintJump(str2);
int w=jump[len];
int ans=0;
for(int i=2;i<len;i++) {
if(jump[i]>ans) ans=jump[i];
}
if(ans>w) ans=w;
printf("%d\n",ans);
}
}
kmp模板题：hdu 2594 Simpsons’ Hidden Talents
在模板的基础上稍微有点小改动
| Description Homer: Marge, I just figured out a way to discover some of the talents we weren’t aware we had. Input Input consists of two lines. The first line contains s1 and the second line contains s2. You may assume all letters are in lowercase. Output Output consists of a single line that contains the longest string that is a prefix of s1 and a suffix of s2, followed by the length of that prefix. If the longest such string is the empty string, then the output should be 0. Sample Input
Sample Output
|
在s2中查找s1，当找到s2结尾时，记录此时s1的下标位置，这就是s1的最长前缀。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXN=50005;
int jump[MAXN];
void PrintJump(char *str)
{
jump[0] = -1;
jump[1] = 0;
int len = strlen(str+1);
int j=1,k;
while(j<len) //计算jump[j+1]
{
k = jump[j]; //已知jump[j]==k
while(k!=-1&&str[k+1]!=str[j+1]) k = jump[k];
jump[j+1] = k+1;
j++;
}
}
int Find(char *s1,char *s2){
int i=0,j=1;
while(1) {
if(s1[i]=='\0') {
return j-1;
}
if(j&&s2[j]=='\0') {
j=jump[j-1]+1;
}
if(j==0||s1[i]==s2[j]) {i++;j++;}
else j = jump[j-1]+1;
}
}
char s1[MAXN],s2[MAXN];
int main()
{
while(scanf("%s%s",s1+1,s2)!=EOF)
{
PrintJump(s1);
int len = Find(s2,s1);
s1[len+1]=0;
if(len==0) puts("0");
else printf("%s %d\n",s1+1,len);
}
}