链接:
http://codeforces.com/problemset/problem/182/D
题目大意:
假设字符串也有因数,一个字符串S的因数是a,当且仅当S是由k个a连续组成的。 例如S="abababab", 那么"ab"和"abab"都是S的因子。
给两个字符串,求它们的公因数有多少个。
分析总结:
先看看一个数的因子有什么性质。
如果知道了一个最小因子,那么就可以利用这个最小因子求出一个字符串的所有因子。
例如,假设S="abababab", len = |S| = 8, 最小因子为A="ab", minlen = |A| = 2, 除了这个最小因子之外,可以发现S的所有因子长度x必须满足len%x==0,并且,还要再满足x%minlen==0。 “abab”就是S的另外一个因子,它满足这个要求。
利用这个性质,就可以解决这道题了。
首先,分别利用kmp的next数组可以求出两个字符串的最小因数。然后用其中一个去匹配另一个,每次可以得到一个当前已匹配长度j,根据这个j,利用上述性质,如果同时满足两个字符串的因子要求,那么就是他们的一个公因子了。具体看代码。
代码:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long int64; const int MAXN = 100005; char S[MAXN], T[MAXN]; int f1[MAXN],f2[MAXN]; bool vis[MAXN]; void getNext(char* P, int* f){ int n=strlen(P); f[0]=f[1]=0; for(int i=1; i<n; ++i){ int j=f[i]; while(j && P[i]!=P[j]) j=f[j]; f[i+1] = P[i]==P[j]?1+j:0; } } int64 find(char* S,char* P,int* f1,int* f2){ getNext(P,f1); getNext(S,f2); memset(vis, 0, sizeof(vis)); int m=strlen(P); int n=strlen(S); int mp=m%(m-f1[m])?m:(m-f1[m]); int ms=n%(n-f2[n])?n:(n-f2[n]); int64 cnt=0; int j=0; for(int i=0; i<n; ++i){ while(j && S[i]!=P[j]) j=f1[j]; if(S[i] == P[j]) ++j; if(j && !vis[j]){ if(m%j==0 && n%j==0 && (i+1)%ms==0 && j%mp==0 && j%ms==0){ // 是否满足公因子性质 ++cnt; vis[j]=true; } } } return cnt; } int main(){ scanf("%s %s",S,T); cout << find(S,T,f1,f2) << endl; return 0; }
—— 生命的意义,在于赋予它意义士。
原创 http://blog.csdn.net/shuangde800 , By
D_Double (转载请标明)