[UOJ 5]【NOI2014】动物园：KMP

本文主要是介绍[UOJ 5]【NOI2014】动物园：KMP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击这里查看原题

cnt[i]表示从i出发，经过cnt[i]次nex[i]到达0。于是做两次KMP，第一次求nex[i]和cnt[i]，第二次求i一直nex[i]到达的第一个≤i/2的位置

/*
User:Small
Language:C++
Problem No.:5
*/
#include<bits/stdc++.h>
#define ll long long
#define inf ((ll)1<<60)
#define pli pair<ll,int>
#define mp make_pair
using namespace std;
const int M=1e6+5;
const ll mod=1e9+7;
ll ans;
int n,nex[M],num[M],sum[M],q[30][M],head[30],tail[30];
char s[M]; 
void solve(){ans=1;scanf("%s",s+1);n=strlen(s+1);memset(nex,0,sizeof(nex));memset(num,0,sizeof(num));memset(tail,0,sizeof(tail));for(int i=0;i<26;i++) head[i]=1;sum[1]=1;for(int i=2;i<=n;i++){int k=nex[i-1];while(k&&s[k+1]!=s[i]) k=nex[k];sum[i]=1;if(s[i]==s[k+1]){nex[i]=k+1;sum[i]=sum[k+1]+1;}}for(int i=2,k=0;i<=n;i++){while(k&&s[k+1]!=s[i]) k=nex[k];if(s[i]==s[k+1]) k++;while(k>i/2) k=nex[k];ans=ans*(sum[k]+1)%mod;}printf("%lld\n",ans);
}
int main(){freopen("data.in","r",stdin);//int t;scanf("%d",&t);while(t--) solve();return 0;
}

这篇关于[UOJ 5]【NOI2014】动物园：KMP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---