[Codeforces Round #445][Codeforces 886D]Restoration of string

    题意：给出n个字符串，要求构造一个字符串S（在长度最短的条件下字典序最小），使得给出的n个字符串都是在S中出现次数最多的子串，不存在则输出"NO"。

    题解：考虑单个字母构成的子串，若给出的字符串中含有两个相同字母，那么该字母出现在S中的次数一定比该字符串多，所以给出的n个字符串各自不能含有相同字母。

    考虑这样两个子串：ab和ac。他们一定不能同时出现，因为若同时出现ab和ac，a就至少出现了两次，所以每个字母后只能跟一个字母。另外如果有类似ab与ba这种构成环的关系也不能存在，否则至少有一个字母出现了两次。

    然后就可以按着这个建图，瞎搞出结果了。

    官方题解写得比较完善（理性），我这里搬来翻译一下：

    1.如果一个字符串在S中是出现次数最频繁的（出现次数最多的），那么它的所有子串出现次数也是最频繁的。

    2.如果字符串ab或者类似的字符串是最频繁的，那么有字母a后面必然是b，字母b前面必然是a。

    3.考虑一个有向图，边a → b存在当且仅当ab是出现次数最频繁的子串。如果有向图中有环，那么满足条件的S不存在。

    4.所以这样的图相当于几条不相交的路径。所有与路径相对应的字符串必须出现在S中。只要我们按字典序将其输出，我们就能得到答案。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;

char s[maxn];
char ans[30];
int cnt[26];
int m0[26],d[26],mp[26];
int n,anslen;

int main()
{
	scanf("%d",&n);
	memset(mp,0xFF,sizeof(mp));
	for (int i=0;i<n;i++)
	{
		scanf("%s",s);
		int len=strlen(s);
		memset(cnt,0,sizeof(cnt));
		for (int j=0;j<len;j++)
		{
			if (cnt[s[j]-'a']++)
			{
				puts("NO");
				return 0;
			}
			if (j<len-1)
			{
				if (mp[s[j]-'a']!=-1 && mp[s[j]-'a']!=s[j+1]-'a')
				{
					puts("NO");
					return 0;
				}
				if (mp[s[j]-'a']==-1) mp[s[j]-'a']=s[j+1]-'a',d[s[j+1]-'a']++;
			}
		}
		m0[s[0]-'a']=1;
	}
	for (int i=0;i<26;i++) if (d[i]) m0[i]=0;
	memset(cnt,0,sizeof(cnt));
	for (int i=0;i<26;i++)
		if (m0[i])
		{
			int t=i;
			while (t!=-1)
			{
				if (++cnt[t]>1)
				{
					puts("NO");
					return 0;
				}
				ans[anslen++]=t+'a';
				t=mp[t];
				if (t!=-1) d[t]--;
			}
		}
	for (int i=0;i<26;i++) if (d[i])
	{
		puts("NO");
		return 0;
	}
	printf("%s\n",ans);
	return 0;
}