【kmp或扩展kmp】HDU 6153 A Secret

acm.hdu.edu.cn/showproblem.php?pid=6153

【题意】

给定字符串A和B,求B的所有后缀在A中出现次数与其长度的乘积之和
A和B的长度最大为1e6

方法一：扩展kmp

【思路】

把A和B同时反转，相当于求B的所有前缀在A中出现次数与其长度的乘积之和
换个角度，相当于A中每出现一个B的前缀，答案中就要加上该前缀的长度
考虑A中每个位置对答案的贡献，A[i...lenA-1]与B的最长公共前缀是x,则B中的前缀B[0...1],B[0....2]...B[0....x]都在A中出现，那么答案就要加上x*(x+1)/2
求S中的每个后缀与T的最长公共前缀用扩展KMP,时间复杂度是线性的

【AC】

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const ll mod=1e9+7;
 5 const int maxn=1e6+2;
 6 char s[maxn];
 7 char t[maxn];
 8 int nxt[maxn];
 9 int extend[maxn];
10 ll ans;
11 
12 void add(ll n)
13 {
14     ll tmp=((n%mod)*((n+1)%mod)/2)%mod;
15     ans=(ans+tmp)%mod;
16 }
17 void pre_EKMP(char x[],int m,int nxt[])
18 {
19     nxt[0]=m;
20     int j=0;
21     while(j+1<m && x[j]==x[j+1]) j++;
22     nxt[1]=j;
23     int k=1;
24     for(int i=2;i<m;i++)
25     {
26         int p=nxt[k]+k-1;
27         int L=nxt[i-k];
28         if(i+L<p+1) nxt[i]=L;
29         else
30         {
31             j=max(0,p-i+1);
32             while(i+j<m && x[i+j]==x[j]) j++;
33             nxt[i]=j;
34             k=i;
35         }
36     }
37 }
38 
39 void EKMP(char x[],int m,char y[],int n,int nxt[],int extend[])
40 {
41     pre_EKMP(x,m,nxt);//子串 
42     int j=0;
43     while(j<n && j<m &&x[j]==y[j]) j++;
44     extend[0]=j;
45     int k=0;
46     for(int i=1;i<n;i++)
47     {
48         int p=extend[k]+k-1;
49         int L=nxt[i-k];
50         if(i+L<p+1) extend[i]=L;
51         else
52         {
53             j=max(0,p-i+1);
54             while(i+j<n && j<m && y[i+j]==x[j]) j++;
55             extend[i]=j;
56             k=i;
57         }
58     }
59 }
60 
61 int main()
62 {
63     int T;
64     scanf("%d",&T);
65     while(T--)
66     {
67         scanf("%s",s);
68         scanf("%s",t);
69         int ls=strlen(s);
70         int lt=strlen(t);
71         for(int i=0;i<ls/2;i++)
72         {
73             swap(s[i],s[ls-1-i]);
74         }
75         for(int i=0;i<lt/2;i++)
76         {
77             swap(t[i],t[lt-1-i]);
78         }
79         EKMP(t,lt,s,ls,nxt,extend);
80         ans=0;
81         for(int i=0;i<ls;i++)
82         {
83             add(extend[i]);
84         }
85         printf("%I64d
",ans);
86     }
87     return 0;
88 }

扩展kmp

方法二：巧用kmp的next数组

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn=1e6+2;
 5 ll id[maxn];
 6 char s[maxn];
 7 char t[maxn];
 8 int nxt[maxn];
 9 const ll mod=1e9+7;
10 void kmp_pre(char x[],int m,int nxt[])
11 {
12     int i,j;
13     j=nxt[0]=-1;
14     i=0;
15     while(i<m)
16     {
17         while(-1!=j && x[i]!=x[j]) j=nxt[j];
18         nxt[++i]=++j;
19     }
20 }
21 
22 int kmp_count(char x[],int m,char y[],int n)
23 {
24     memset(id,0,sizeof(id));
25     int i,j;
26     ll ans=0;
27     kmp_pre(x,m,nxt);
28     i=j=0;
29     while(i<n)
30     {
31         while(-1!=j && y[i]!=x[j]) 
32             j=nxt[j];
33         i++;
34         j++;
35         if(i>=n) break;
36         //失配时记录当前匹配的最长前缀 
37         if(y[i]!=x[j])
38         {
39             id[j]++;
40         }
41         if(j>=m)
42             j=nxt[j];
43     }
44     //s的结尾出有一段和匹配的，由于i已经达到n没有记录，用t本身的nxt算出 
45     while(j!=-1)
46     {
47         id[j]++;
48         j=nxt[j];
49     }
50     for(int i=1;i<=m;i++)
51     {
52         if(id[i])
53         {
54             ans=(ans+(1ll*i*(i+1)/2)%mod*id[i]%mod)%mod;
55         }
56     }
57     return ans;
58 }
59 int main()
60 {
61     int T;
62     scanf("%d",&T);
63     while(T--)
64     {
65         scanf("%s",s);
66         scanf("%s",t);
67         int ls=strlen(s);
68         int lt=strlen(t);
69         reverse(s,s+ls);
70         reverse(t,t+lt);
71         ll res=kmp_count(t,lt,s,ls);
72         cout<<res<<endl;
73     }
74     return 0;
75 }

kmp