HDU 6740 kmp最小循环节

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define il inline
 5 #define it register int
 6 #define inf 0x3f3f3f3f
 7 #define lowbit(x) (x)&(-x)
 8 #define mem(a,b) memset(a,b,sizeof(a))
 9 #define mod 998244353
10 const int maxn=1e7+10;
11 ll n,m;
12 int nexts[maxn];
13 char s[maxn],s2[maxn];
14 int p2=0;
15 il void GetNext(int l){
16     int i=0;
17     int j=-1;
18     nexts[0]=-1;
19     while(i<l){
20         if(j==-1 || s2[i]==s2[j]){
21             i++;
22             j++;
23             nexts[i] = j;
24         }
25         else
26             j = nexts[j];
27     }
28     return;
29 }
30 int main(){
31     while(~scanf("%lld%lld",&n,&m)){
32         scanf("%s",s);
33         int l=strlen(s);p2=0;
34         int i;
35         for(i=0;i<l;i++){
36             if(s[i]==‘.‘){
37                 break;
38             }
39         }
40         for(int k=l-1;k>i;k--){
41             s2[p2++]=s[k];
42         }
43         GetNext(p2);
44         ll maxx=-1e18;
45         for(i=1;i<=p2;i++){
46             maxx=max(maxx,(ll)i*n-(ll)(i-nexts[i])*m);
47             //cout<<i<<" "<<(i-nexts[i])<<endl;
48         }
49         printf("%lld\n",maxx);
50     }
51     return 0;
52 }

 1 inline void getnext(char *ss){
 2     mem(ne,0);
 3     int l=strlen(ss);
 4     int i=0,j=-1;ne[0]=-1;
 5     while(i<l){
 6         if (j == -1 || ss[i] == ss[j])
 7         {
 8             i++;
 9             j++;
10             ne[i] = j;
11         }
12         else{
13             j = ne[j];
14         }
15     }
16     return;
17 }
18 inline int kmp(char *ss,char *s){
19     int l=strlen(s),ls=strlen(ss);
20     int i=0,j=0,ans=0;
21     while(i<l){
22         if(j==-1||s[i]==ss[j])
23         {
24             i++;
25             j++;
26         }
27         else
28             j=ne[j];
29         if(j==ls)
30         {
31             ans++;
32             j=ne[j];
33         }
34     }
35     return ans;
36 }