标签：模拟，hash
There are n phone numbers in Polycarp's contacts on his phone. Eachnumber is a 9-digit integer, starting with a digit different from 0. All the numbers aredistinct.
There is the latest version of Berdroid OS installed onPolycarp's phone. If some number is entered, is shows up all the numbers in thecontacts for which there is a substring equal to the entered sequence ofdigits. For example, is there are three phone numbers in Polycarp's contacts: 123456789, 100000000 and 100123456, then:
· if he enters 00 two numbers will show up: 100000000 and 100123456,
· if he enters 123 two numbers will show up 123456789 and 100123456,
· if he enters 01 there will be only one number 100123456.
For each of the phone numbers in Polycarp's contacts,find the minimum in length sequence of digits such that if Polycarp enters thissequence, Berdroid shows this only phone number.
Input
The first line contains single integer n (1 ≤ n ≤ 70000) — the total number of phone contacts in Polycarp'scontacts.
The phone numbers follow, one in each line. Each numberis a positive 9-digit integer starting with a digit from 1 to 9. All the numbers are distinct.
Output
Print exactly n lines: the i-th of themshould contain the shortest non-empty sequence of digits, such that if Polycarpenters it, the Berdroid OS shows up only the i-th numberfrom the contacts. If there are several such sequences, print any of them.
Examples
input
3
123456789
100000000
100123456
output
9
000
01
input
4
123456789
193456789
134567819
934567891
output
2
193
81
91
题意：截取每个字符串中具有代表性的最短非空子串
分析：昨晚打CF的时候，看到这题就一直往KMP，trie树那些高级字符串算法想去了
然而今早补题的时候，才发现用hash就完全可以，或者可以直接模拟
Code
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int maxn=70005,maxm=1000005;
int t[maxm][12],tt=0,c[maxm],v[maxm];
char s[maxn][12];
void ins(char *s,int q)
{
int p=0;
for(;*s;s++){
if(t[p][*s-'0']==0)t[p][*s-'0']=++tt;
p=t[p][*s-'0'];
if(v[p]!=q){c[p]++;v[p]=q;}//更新计数数组c和最新的记录位置数组v
}
return;
}
int find(char *s)
{
int p=0,l=0;
for(;*s;s++){
l++;
p=t[p][*s-'0'];
if(c[p]==1)return l;//返回最小长度
}
return 10;
}
int main()
{
int n;
scanf("%d",&n);
memset(v,-1,sizeof v);
rep(i,0,n-1){
scanf("%s",s[i]);
rep(j,0,8){ins(s[i]+j,i);}//建立查询的数组
}
rep(i,0,n-1){
int start=0,len=9;
rep(j,0,8){
int u=find(s[i]+j);//查询长度，如果小于答案，更换答案
if(u<len){
start=j;
len=u;
}
}
s[i][start+len]=0;
printf("%s\n",s[i]+start);
}
return 0;
}
