最初思路

看到这道题，我首先想到的是动态规划。对三次匹配分别开维度，定义状态为：$f_{i,j,posj,k,posk}$ 表示最短串长度。其中 $i$，$j$，$k$ 分别表示三次匹配当前的串，而 $posj$，$posk$ 表示匹配的位数。

这样定义状态无法实现，有几个原因：

1. 需要空间约为 $n ^ 3 \times |s| ^ 2$ 有些紧张。
2. 转移时还需 $O(n)$ 时间，会超时。
3. 转移顺序无法明确。

改进优化

进一步观察发现，实际上状态并没有定义的那么多，也就是跑不满，所以用 map 存状态。转移顺序的问题可以通过 bfs 解决。

在实现时，也不需要专门维护“三次”匹配，而是注重对于每一个当前答案，它仍然能够匹配上的是哪些串以及这些串匹配到了哪一位。

在每一次更新当前答案时，如果有一个串被完全匹配，则把 num 增大 $1$ 最后看 num 的值如果 $\ge3$ 说明找到正确答案。

代码

常数大亿点，但较容易看，能 AC

#include <bits/stdc++.h>
using namespace std;
typedef vector<pair<int,int> > vpi;
//pair 的 first 为串的编号，second 为匹配位数
const int N=35,L=55;
int n;
string s[N];
vpi x,y,t;
map<vpi,int>mp;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
		if(s[i].length()==0)return cout<<0,0;//特判空串
		x.push_back(make_pair(i,0));
	}
	queue<vpi>q;
	q.push(x);mp[x]=0;
	while(!q.empty())
	{
		x=q.front();q.pop();
		int now=mp[x],num;
		for(char c='0';c<='1';c++)
		{
			y.clear();num=0;
			for(int i=0;i<x.size();i++)
			{
				int id=x[i].first,nid=x[i].second;
				if(s[id][nid]!=c)continue;
				++nid;//要匹配下一位了
				if(nid==s[id].size())//完全匹配，所有串都有可能成为下一个状态
				{
					++num;
					for(int j=1;j<=n;j++)y.push_back(make_pair(j,0));
				}
				else y.push_back(make_pair(id,nid));//匹配了部分，继续匹配
			}
			if(num>=3)return cout<<now+1,0;//找到答案，结束程序
			if(y.size()&&!mp[y])mp[y]=now+1,q.push(y);
		}
	}
	cout<<-1;
	return 0;
}