A Secret HDU

A Secret

题意：给两个串s1,s2,问s2的所有后缀在s1中出现的次数乘以后缀长度的和是多少。

首先将串翻转，然后KMP即可。

通过这个题我也认识到对很多简单的算法理解的不够深刻，学了也就只会耍耍模板，以后要多思考思考。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const int maxn=1e6+10;
 5 const int mod=1e9+7;
 6 char s[maxn],p[maxn];
 7 int f[maxn];
 8 int lens,lenp;
 9 ll ans;
10 
11 void getfail(char* p){
12     f[0]=f[1]=0;
13     for(int i=1;i<lenp;i++){
14         int j=f[i];
15         while(j&&p[i]!=p[j]) j=f[j];
16         f[i+1]=p[i]==p[j]?j+1:0;
17     }
18     return ;
19 }
20 
21 void KMP(char* s,char* p){
22     getfail(p);
23     ll j=0;
24     for(ll i=0;i<lens;i++){
25         while(j&&s[i]!=p[j]) {
26             ans=(ans+(j+1)*j/2)%mod;
27             j=f[j];
28         }
29         if(s[i]==p[j]) j++;
30         if(j==lenp){
31             ans=(ans+(j+1)*j/2)%mod;
32             j=f[j];
33         }
34     }
35     while(j){
36       ans=(ans+j*(j+1)/2)%mod;
37       j=f[j];
38     }
39     return ;
40 }
41 
42 int main(){
43     int t;
44     scanf("%d",&t);
45     while(t--){
46         ans=0;
47         scanf("%s%s",s,p);
48         lens=strlen(s);
49         lenp=strlen(p);
50         reverse(s,s+lens);
51         reverse(p,p+lenp);
52         KMP(s,p);
53         printf("%lld
",ans);
54     }
55     return 0;
56 }

View Code

上面的代码虽然过了，可是对于这组数据答案是错的=_=

baabaa

caabaa

看到了扩展KMP~去学习下再来补~

是可以用扩展KMP秒掉的~

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const int maxn=1e6+10;
 5 const int mod=1e9+7;
 6 
 7 char s[maxn],t[maxn];
 8 int nex[maxn],ex[maxn];
 9 int lens,lent;
10 void getnex(char* t){
11     nex[0]=lent;
12     int a=0,p=0;
13     for(int i=1;i<lent;i++){
14         if(i>=p||i+nex[i-a]>=p){
15             if(i>=p) p=i;
16             while(p<lent&&t[p]==t[p-i]) p++;
17             nex[i]=p-i;
18             a=i;
19         }else nex[i]=nex[i-a];
20     }
21 }
22 void exkmp(char* s,char* t){
23     getnex(t);
24     int a=0,p=0;
25     for(int i=0;i<lens;i++){
26         if(i>=p||i+nex[i-a]>=p){
27             if(i>=p) p=i;
28             while(p<lens&&p-i<lent&&s[p]==t[p-i]) p++;
29             ex[i]=p-i;
30             a=i;
31         }else ex[i]=nex[i-a];
32     }
33 }
34 int main(){
35     int T;
36     scanf("%d",&T);
37     while(T--){
38         scanf("%s%s",s,t);
39         lens=strlen(s);
40         lent=strlen(t);
41         reverse(s,s+lens);
42         reverse(t,t+lent);
43         exkmp(s,t);
44         ll ans=0;
45         for(int i=0;i<lens;i++) if(ex[i]) ans=(ans+1ll*(ex[i]+1)*ex[i]/2)%mod;
46         printf("%lld
",ans);
47     }
48 }

View Code