題目鏈接：點擊查看

題目大意：給出兩個字符串s和t，求這兩個字符串有多少個公因子，規(guī)定若字符串n為其公因子，則：

設(shè)lens是字符串s的長度，lent是字符串t的長度，lenn是字符串n的長度，需要滿足lent%n==0&&lens%n==0

字符串n必須在字符串s中出現(xiàn)lens/lenn次，在字符串t中出現(xiàn)lent/lenn次

題目分析：這個題目主要是有點抽象，經(jīng)過上面的翻譯就好懂很多了，我們只要求出滿足上述條件的所有字符串n即可，那么現(xiàn)在問題來了，該怎么求呢？其實不難發(fā)現(xiàn)，所有的因子，都是基于字符串s和t的最小公因子，通過上述概念，我們不難延伸出兩個字符串最小公因子的定義，換一種說法，也就是兩個字符串的最小循環(huán)節(jié)

我們可以通過先求出兩個字符串s和t的最大循環(huán)節(jié)長度，首先必須滿足兩個字符串是周期性字符串，然后再判斷一下兩者是否相等，若不相等則肯定不可能有最小公因子了，就更別說公因子了，若相等的話繼續(xù)判斷一下其循環(huán)節(jié)是否相等，若上述條件都滿足的話，兩個字符串的最小相同循環(huán)節(jié)就是其最小公因子了，我們通過給最小公因子不斷加倍，就可以獲得一共有多少個因子了，因為上面已經(jīng)判斷兩個字符串都是周期性字符串了，所以到這里我們只需要根據(jù)長度來判斷條件就可以了，每次讓公因子的長度都增加最小循環(huán)節(jié)的長度，若當前的長度為i，則lens%i==0&&lent%i==0就說明當前的因子屬于兩者的公因子，讓答案加一即可

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef unsigned long long ull;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;string s1,s2;int nxa[N],nxb[N];void getnext(string s,int nx[]) {nx[0]=-1;int i=0,j=-1;while(i<s.size()){if(j==-1||s[i]==s[j])nx[++i]=++j;elsej=nx[j];} }int main() { // freopen("input.txt","r",stdin);ios::sync_with_stdio(false);cin>>s1>>s2;getnext(s1,nxa);getnext(s2,nxb);int na=s1.size();int nb=s2.size();int lena=na-nxa[na];if(na%lena!=0)//若不是周期性字符串，就讓其長度等于本身lena=na;int lenb=nb-nxb[nb];if(nb%lenb!=0)lenb=nb;if(lena!=lenb)//如果兩個字符串的最小循環(huán)節(jié)長度不相等，則肯定沒有公因子cout<<0<<endl;else{string temp1=s1.substr(0,lena);//最小公因子 string temp2=s2.substr(0,lenb);if(temp1!=temp2)//如果最小循環(huán)節(jié)不相等，則肯定沒有公因子cout<<0<<endl;else{int ans=0;for(int i=lena;i<=na&&i<=nb;i+=lena)//求一下有多少個最小公因子的倍數(shù)滿足兩者的公因子{if(na%i==0&&nb%i==0)ans++;}cout<<ans<<endl;}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 182D Common Divisors(KMP的next数组)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。