5335: 构造字符串
[Creator : ]
Description
给定若干个小写英文字母,请你用这些英文字母组成 nnn 个字符串,字符串可以是空串。要求这 nnn 个字符串的最长公共前缀最长。求出这个最长的长度。
所有字母都要用完,且每个字母只能用在一个字符串里。
前缀 是指一个字符串从第一个字符开始的连续若干个字符组成的字符串。前缀可以为空串。比如字符串"aab"的前缀有四个,分别是"","a","aa","aab"
我们说一个字符串 sss 是某些串的 公共前缀,当且仅当这个串是每个字符串的 前缀。
每一个 公共前缀 都是一个字符串,是字符串就有长度。当 nnn 个串都确定下来的时候,这 nnn 个串的所有 公共前缀 也就确定下来了,而且可以证明 公共前缀 的数目是有限的,在这有限个 公共前缀 中,有一个 公共前缀 的长度是最长的,这个前缀就是 最长公共前缀。
举个例子,假设现在有三个串:
再举个例子,假设现在有四个串:
所有字母都要用完,且每个字母只能用在一个字符串里。
前缀 是指一个字符串从第一个字符开始的连续若干个字符组成的字符串。前缀可以为空串。比如字符串"aab"的前缀有四个,分别是"","a","aa","aab"
我们说一个字符串 sss 是某些串的 公共前缀,当且仅当这个串是每个字符串的 前缀。
每一个 公共前缀 都是一个字符串,是字符串就有长度。当 nnn 个串都确定下来的时候,这 nnn 个串的所有 公共前缀 也就确定下来了,而且可以证明 公共前缀 的数目是有限的,在这有限个 公共前缀 中,有一个 公共前缀 的长度是最长的,这个前缀就是 最长公共前缀。
举个例子,假设现在有三个串:
abbc abbde abbe这个三个串的最长公共前缀是"abb",长度为 333
再举个例子,假设现在有四个串:
abbd bbd abbd abb那么这四个串的最长公共前缀是"",长度为 000
Input
输入共有两行
第一行是一个整数 nnn ,表示字符串的数量
第二行包含 262626 个非负整数。从前往后依次表示你拥有字母 aaa 的数目,字母 bbb 的数目,.........,字母 zzz 的数目。
第一行是一个整数 nnn ,表示字符串的数量
第二行包含 262626 个非负整数。从前往后依次表示你拥有字母 aaa 的数目,字母 bbb 的数目,.........,字母 zzz 的数目。
Output
输出一个非负整数,表示答案。
Sample 1 Input
2
3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Sample 1 Output
2