CF858D Polycarp's phone book

题意翻译

有 n 个长度为 9 且只包含数字字符互不相同的串。

需要对于每个串找到一个长度最短的识别码，使得这个识别码当且仅当为这个串的子串。

题目分析

因为范围不是非常大，所以可以将子串筛出来

然后用STL统计即可

#include<bits/stdc++.h>
using namespace std;
int n;
string s[70005];
map<string,vector<int> >rec;
map<string,int >vis;
vector<string>cklfuck[70005];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
		vis.clear();
		for(int j=0;j<s[i].size();j++)
		{
			string ckl;
			for(int k=j;k<s[i].size();k++)
			{
				ckl+=s[i][k];
				if(!vis[ckl])
				{
					vis[ckl]=1;
					rec[ckl].push_back(i);
				}
				
			}
			
		}
	}
	for(map<string,vector<int> >::iterator it=rec.begin();it!=rec.end();it++)
	{
		pair<string,vector<int> >pi=(*it);
		vector<int>saeds=pi.second;
		if(saeds.size()==1)
		{
			string sf=(*it).first;
			vector<int>::iterator id=saeds.begin();
			int key=*id;
			cklfuck[key].push_back(sf);
		}
	}
	for(int i=1;i<=n;i++)
	{
		int mini=0x3f3f3f3f;
		int keyi;
		for(int j=0;j<cklfuck[i].size();j++)
		{
			string cjg=cklfuck[i][j];
			if(mini>cjg.size())
			{
				mini=cjg.size();
				keyi=j;	
			}	
//			cout<<cklfuck[i][j];
//			printf("\n");
		}		
		cout<<cklfuck[i][keyi];
		printf("\n");
	}
}

CF858D Polycarp's phone book

原文：https://www.cnblogs.com/kid-magic/p/15004805.html