编程介的小学生 2017-01-16 06:25 采纳率: 20.5%
浏览 1369
已采纳

最短前缀

描述
一个字符串的前缀是从该字符串的第一个字符起始的一个子串。例如 "carbon"的字串是: "c", "ca", "car", "carb", "carbo", 和 "carbon"。注意到这里我们不认为空串是字串, 但是每个非空串是它自身的字串. 我们现在希望能用前缀来缩略的表示单词。例如, "carbohydrate" 通常用"carb"来缩略表示. 现在给你一组单词, 要求你找到唯一标识每个单词的最短前缀
在下面的例子中，"carbohydrate" 能被缩略成"carboh", 但是不能被缩略成"carbo" (或其余更短的前缀) 因为已经有一个单词用"carbo"开始
一个精确匹配会覆盖一个前缀匹配，例如，前缀"car"精确匹配单词"car". 因此 "car" 是 "car"的缩略语是没有二义性的 , “car”不会被当成"carriage"或者任何在列表中以"car"开始的单词.
输入
输入包括至少2行，至多1000行. 每行包括一个以小写字母组成的单词，单词长度至少是1，至多是20.
输出
输出的行数与输入的行数相同。每行输出由相应行输入的单词开始，后面跟着一个空格接下来是相应单词的没有二义性的最短前缀标识符。
样例输入
carbohydrate
cart
carburetor
caramel
caribou
carbonic
cartilage
carbon
carriage
carton
car
carbonate
样例输出
carbohydrate carboh
cart cart
carburetor carbu
caramel cara
caribou cari
carbonic carboni
cartilage carti
carbon carbon
carriage carr
carton carto
car car
carbonate carbona

  • 写回答

2条回答 默认 最新

  • shen_wei 2017-01-16 06:52
    关注

    "carbohydrate" 能被缩略成"carboh", 但是不能被缩略成"carbo" (或其余更短的前缀) 因为已经有一个单词用"carbo"开始

    如果是这样的话，那就得建立英语单词库了。。不然的话那就不知道如何去缩写了！！

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题？

  • 最短前缀
    2017-01-16 06:25
    回答 2 已采纳 "carbohydrate" 能被缩略成"carboh", 但是不能被缩略成"carbo" (或其余更短的前缀) 因为已经有一个单词用"carbo"开始 如果是这样的话，那就得建立英语单词库了。
  • 为什么这个代码没有输出啊，oj中的最短前缀问题 c语言
    2022-05-08 16:09
    回答 1 已采纳 你的程序一直停在了 while(scanf("%s",s[count])!=EOF) { count++; }所以没看到输出，你可以在while循环后面加一行打印，就会
  • Python self前缀 python
    2022-12-11 17:37
    回答 2 已采纳 望采纳在 Python 中，如果要访问一个对象的属性或者方法，通常需要在属性或方法名前面加上 self 前缀。这个 self 前缀的作用是表示当前对象本身，也就是说，如果在一个对象的方法中，你要访问这
  • c语言最短前缀问题，简单循环
    2021-07-27 20:09
    c语言最短前缀问题，简单循环
  • 前缀和问题，HELP！ c++ 有问必答
    2022-05-15 10:26
    回答 2 已采纳 #include<bits/stdc++.h> using namespace std; void shuru(int ,int *); void shuchu(int ,int *,
  • mysql的自增id如何加前缀 java java-ee mysql
    2021-04-11 09:54
    回答 1 已采纳 做不到，按照日期去自增，除非你程序自己生成写入。 相近的方法，可以每天插入一条初始记录，初始记录为2021041100之类的； 还有一种就是，设置两个字段，自增ID字段，和日期 两个字段，在这两个
  • c语言. 前缀码判断。 c语言 有问必答
    2021-12-26 17:15
    回答 3 已采纳 https://blog.csdn.net/liuyi005/article/details/41855735
  • 最短前缀
    2020-03-14 10:14
    lwz_159的博客 一个字符串的前缀是从该字符串的第一个字符起始的一个子串。例如 "carbon"的字串是: “c”, “ca”, “car”, “carb”, “carbo”, 和 “carbon”。注意到这里我们不认为空串是字串, 但是每个非空串是它自身的字串....
  • Pandas合并前缀类似的行 python 数据分析
    2023-01-28 16:38
    回答 2 已采纳 新年好，这边梳理一下解决思路。望采纳1、数据 ---- 我们现在有几千条处理后的数据2、目标 ： 根据第一列"最长前缀" 来进行合并，比如‘abcde’与‘abcdf’，abcd这个前缀相同。解决思路
  • struct_前缀vs无前缀
    2018-03-16 15:09
    回答 1 已采纳 You are declaring your C struct as a typedef and not as a named struct. In your c code you have s
  • 关于加权前缀和的问题 c++ c语言
    2022-12-09 11:46
    回答 2 已采纳 你计算加权的部分感觉有点复杂，我想是你把求和和录入数组放在了一起的原因，其实可以分开，这样方便也不容易出错。所以建议换这种更清晰好懂的写法：用数组a来存放数列的每一个项第二次输入1，i，j则循环累加a
  • POJ 2797 最短前缀（贪心算法）
    2019-08-03 15:28
    Vax_Loves_1314的博客 题目：最短前缀 一个字符串的前缀是从该字符串的第一个字符起始的一个子串。例如 "carbon"的字串是: "c", "ca", "car", "carb", "carbo", 和 "carbon"。注意到这里我们不认为空串是字串, 但是每个非空串是它自身的...
  • 关于数组带前缀信息问题 java
    2023-04-09 16:37
    回答 2 已采纳 这是输出语句，看似要输出数组a，但只能打印数组a的 类型加上hashcode，因为java中任何对象都是继承的Object父类，它有个toString 方法，正是输出语句println方法会调用的。要
  • 2797:最短前缀
    2018-10-10 14:18
    NIL_的博客 //查找 前缀个数为1 的就是最短 #include #include #include typedef struct Trie{ trie *next[26]; int num;//有多少个单词的前缀 }trie; trie root; //初始化 void init(trie* node){ for(int i=0;i;i++) ...
  • Shortest Prefixes 最短前缀（c语言）
    2022-04-17 22:10
    克里斯蒂亚诺.CR7的博客 在此问题中，给定一组单词，您将为每个单词找到唯一标识其所表示的单词的最短前缀。 在下面的示例输入中，“碳水化合物”可以缩写为“carboh”，但不能缩写为“carbo”（或任何更短的东西），因为列表中还有其他单词...
  • 没有解决我的问题, 去提问

悬赏问题

  • ¥15 关于#python#的问题：求帮写python代码
  • ¥20 MATLAB画图图形出现上下震荡的线条
  • ¥15 LiBeAs的带隙等于0.997eV,计算阴离子的N和P
  • ¥15 关于#windows#的问题：怎么用WIN 11系统的电脑 克隆WIN NT3.51-4.0系统的硬盘
  • ¥15 来真人，不要ai！matlab有关常微分方程的问题求解决，
  • ¥15 perl MISA分析p3_in脚本出错
  • ¥15 k8s部署jupyterlab，jupyterlab保存不了文件
  • ¥15 ubuntu虚拟机打包apk错误
  • ¥199 rust编程架构设计的方案 有偿
  • ¥15 回答4f系统的像差计算