Description
You are given n strings s1, s2, ..., sn consisting of characters 0 and 1. m operations are performed, on each of them you concatenate two existing strings into a new one. On the i-th operation the concatenation saisbi is saved into a new string sn + i (the operations are numbered starting from 1). After each operation you need to find the maximum positive integer k such that all possible strings consisting of 0 and 1 of length k (there are 2k such strings) are substrings of the new string. If there is no such k, print 0.
解题报告
这题对于合并的两个串的操作，新串对两个合并的串连边，由于每一次长度最多翻一倍，也就是最长为 (2^{100}) ，所以 (k) 长度也不超过100，所以可以分治处理，那么新串就可以只存新串的长度为100的部分，也就是说 左边部分的后k个和右边部分的前k个需要单独算贡献，内部的贡献直接分治处理，枚举 (k)，然后直接哈希字符串判断出现次数，并记录串的个数是否等于 (2^k) 即可
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=205;
string s[N][2];int len[N],n,ls[N],rs[N],m,tot=0;
map<string,int>re;bool vis[N];
void dfs(int x,int k){
if(vis[x])return ;vis[x]=true;
if(!rs[x]){
for(int i=0;i+k<=len[x];i++){
string w=s[x][0].substr(i,k);
if(!re[w]){
re[w]++;tot++;
}
}
return ;
}
string S=s[ls[x]][1]+s[rs[x]][0];
int li=S.size();
for(int i=0;i+k<=li;i++){
string w=S.substr(i,k);
if(!re[w]){
re[w]++;tot++;
}
}
dfs(ls[x],k);dfs(rs[x],k);
}
bool check(int k,int x){
memset(vis,0,sizeof(vis));re.clear();tot=0;
dfs(x,k);
if(tot==(1<<k))return true;
return false;
}
void work()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
cin>>s[i][0];
s[i][1]=s[i][0];
ls[i]=rs[i]=0;
len[i]=s[i][0].size();
}
scanf("%d",&m);
for(int i=n+1;i<=n+m;i++){
scanf("%d%d",&ls[i],&rs[i]);
s[i][0]=s[ls[i]][0];
if(len[ls[i]]<=100)s[i][0]=s[i][0]+s[rs[i]][0];
if(s[i][0].size()>=100)s[i][0]=s[i][0].substr(0,100);
s[i][1]=s[ls[i]][1];
if(len[rs[i]]<=100)s[i][1]=s[i][1]+s[rs[i]][1];
if(s[i][1].size()>=100)s[i][1]=s[i][1].substr(s[i][1].size()-100,100);
int k=1;
for(k=1;k<=100;k++){
if(!check(k,i))break;
}
printf("%d
",k-1);
}
}
int main()
{
work();
return 0;
}