题目链接
题目大意
n个字符串
组合成一个新的无限字符串 组成规则是每个字符串依次出一个字符
例如
s1 = abc, s2 = bd.as follows: abbdcbad...
问你最少几个字符长度就可以将所有出现过的字符包括
题目思路
求出最小的新组合字符snow长度然后进行单调尺取即可
对于新组合字符串长度 设新长度为snow=1
逐个字符串长度与snow计算最大公因数 然后除公因数求出snow为单个串的长度
snow*n为n个字符串的总长度 最后再给他重复一遍防止漏判
代码
#include<stdio.h>
#include<iostream>
#include<sstream>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<vector>
#include<bitset>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cctype>
#include<stack>
#include<set>
#include<map>
using namespace std;
typedef long long int ll;
const double pi=acos(-1.0);
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const int maxn=2e4+10;
const int maxm=6e6+10;
int t,n;
string s[maxn];
char c[maxm];
int vis[30];
int cx[30];
void init()
{memset(cx,0,sizeof cx);memset(c,0,sizeof c);
}int gcd(int a,int b)
{return b==0?a:gcd(b,a%b);
}
int main()
{cin>>t;while(t--){cin>>n;init();int maxs=0;int maxpos;ll now=1;for(int i=1;i<=n;i++){cin>>s[i];now=now*s[i].size()/gcd(now,s[i].size());if(maxs<s[i].size()){maxs=s[i].size();maxpos=i;}} int num=0;int cnt=0;int flag=1;now=now*n*2;//cout<<now<<endl;for(int i=1;;i++){for(int j=1;j<=n;j++){int sz=s[j].size(); c[++num]=s[j][(i-1)%sz];int tmp=c[num]-'a'+1;if(cx[tmp]==0){cnt++;}cx[tmp]=1;if(num>=now)//造到长度为now即可 {flag=0;break;}}if(flag==0)break;}//printf("%s\n",c+1);int ans=1e9;memset(vis,0,sizeof vis);int nownum=0;int l=1;for(int r=1;r<=now;r++){int tmp=c[r]-'a'+1;//单调尺取判断 if(vis[tmp]==0)nownum++;vis[tmp]++;int tmpl=c[l]-'a'+1;while(vis[tmpl]>1){l++;vis[tmpl]--;tmpl=c[l]-'a'+1;}if(nownum==cnt){ans=min(ans,r-l+1);}}cout<<ans<<endl;}return 0;
}