首页 > 代码库 > hdu3336 kmp

hdu3336 kmp

2024-09-20 00:20:50   218人阅读

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. 

InputThe 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. 
OutputFor 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数值往前递归加上次数，最后就是结果，交了之后发现tle（没有发现最差的时间复杂度居然有O（n*n）），于是乎只能改进一下，用num数组来存次数，每次递归的时候就把当前num++，这样只需要遍历一遍就行了
时间复杂度变成了O（n）果然不会Tle了
技术分享 
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<iomanip>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define ll long long
#define mod 10007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1

using namespace std;

const double g=10.0,eps=1e-9;
const int N=200000+5,maxn=60+5,inf=0x3f3f3f3f;

ll num[N];
int Next[N],slen;
string str;

void getnext()
{
    int k=-1;
    Next[0]=-1;
    for(int i=1;i<slen;i++)
    {
        while(k>-1&&str[k+1]!=str[i])k=Next[k];
        if(str[k+1]==str[i])k++;
        Next[i]=k;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
 //   cout<<setiosflags(ios::fixed)<<setprecision(2);
    int t,n;
    cin>>t;
    while(t--){
        cin>>n>>str;
        slen=str.size();
        getnext();
        ll ans=0;
        memset(num,0,sizeof num);
        for(int i=slen-1;i>=0;i--)
        {
            ll j=i;
            while(j!=-1)num[j]++,j=Next[j];
        }
        for(int i=0;i<slen;i++)ans=ans%mod+num[i]%mod;
        cout<<ans<<endl;
    }
    return 0;
}
View Code

 

hdu3336 kmp


联系
我们