CodeForces - 182D Common Divisors(KMP的next数组)

题目链接：点击查看

题目大意：给出两个字符串s和t，求这两个字符串有多少个公因子，规定若字符串n为其公因子，则：

设lens是字符串s的长度，lent是字符串t的长度，lenn是字符串n的长度，需要满足lent%n==0&&lens%n==0

字符串n必须在字符串s中出现lens/lenn次，在字符串t中出现lent/lenn次

题目分析：这个题目主要是有点抽象，经过上面的翻译就好懂很多了，我们只要求出满足上述条件的所有字符串n即可，那么现在问题来了，该怎么求呢？其实不难发现，所有的因子，都是基于字符串s和t的最小公因子，通过上述概念，我们不难延伸出两个字符串最小公因子的定义，换一种说法，也就是两个字符串的最小循环节

我们可以通过先求出两个字符串s和t的最大循环节长度，首先必须满足两个字符串是周期性字符串，然后再判断一下两者是否相等，若不相等则肯定不可能有最小公因子了，就更别说公因子了，若相等的话继续判断一下其循环节是否相等，若上述条件都满足的话，两个字符串的最小相同循环节就是其最小公因子了，我们通过给最小公因子不断加倍，就可以获得一共有多少个因子了，因为上面已经判断两个字符串都是周期性字符串了，所以到这里我们只需要根据长度来判断条件就可以了，每次让公因子的长度都增加最小循环节的长度，若当前的长度为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)//如果两个字符串的最小循环节长度不相等，则肯定没有公因子cout<<0<<endl;else{string temp1=s1.substr(0,lena);//最小公因子 string temp2=s2.substr(0,lenb);if(temp1!=temp2)//如果最小循环节不相等，则肯定没有公因子cout<<0<<endl;else{int ans=0;for(int i=lena;i<=na&&i<=nb;i+=lena)//求一下有多少个最小公因子的倍数满足两者的公因子{if(na%i==0&&nb%i==0)ans++;}cout<<ans<<endl;}}return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 182D Common Divisors(KMP的next数组)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。