描述

　　一個(gè)字符串的前綴是從該字符串的第一個(gè)字符起始的一個(gè)子串。例如 "carbon"的字串是: "c", "ca", "car", "carb", "carbo", 和 "carbon"。注意到這里我們不認(rèn)為空串是字串, 但是每個(gè)非空串是它自身的字串. 我們現(xiàn)在希望能用前綴來縮略的表示單詞。例如, "carbohydrate" 通常用"carb"來縮略表示. 現(xiàn)在給你一組單詞, 要求你找到唯一標(biāo)識每個(gè)單詞的最短前綴
在下面的例子中，"carbohydrate" 能被縮略成"carboh", 但是不能被縮略成"carbo" (或其余更短的前綴) 因?yàn)橐呀?jīng)有一個(gè)單詞用"carbo"開始
一個(gè)精確匹配會覆蓋一個(gè)前綴匹配，例如，前綴"car"精確匹配單詞"car". 因此 "car" 是 "car"的縮略語是沒有二義性的 , “car”不會被當(dāng)成"carriage"或者任何在列表中以"car"開始的單詞.
輸入輸入包括至少2行，至多1000行. 每行包括一個(gè)以小寫字母組成的單詞，單詞長度至少是1，至多是20.輸出輸出的行數(shù)與輸入的行數(shù)相同。每行輸出由相應(yīng)行輸入的單詞開始，后面跟著一個(gè)空格接下來是相應(yīng)單詞的沒有二義性的最短前綴標(biāo)識符。

樣例輸入

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

暴力的做法 ：遍歷每個(gè)單詞可能的前綴 ，并在其他單詞從搜索， 如果包含在其他某個(gè)單詞的前面， 就不能作為前綴 ，搜尋下一個(gè)可能的前綴。
　　　　　　如果所有可能的前綴都在其他某個(gè)含有就是其本身。
#include <iostream> #include <stdio.h> #include <string> #include <cstring> using namespace std;char w[1010][45]; char pre[22]; int n;bool in(char *s, int index) {for (int i = 0; i < n; i++) {if (strcmp(s, w[index]) == 0)return 0;if (i == index)continue;if (strstr(w[i], s)== &w[i][0])return 1;}return 0; }int main() {//freopen("1.txt", "r", stdin);n = 0;while (~scanf("%s", w[n++]));for (int i = 0; i < n; i++) {for (int j = 0; j < strlen(w[i]); j++) {memset(pre, 0, sizeof(pre));strncpy(pre, w[i], j+1);if (!in(pre, i)) {strcat(w[i], " ");strcat(w[i], pre);break;}}}for (int i = 0; i < n; i++)puts(w[i]);return 0; }

也可利用Trie，字典樹?

先建樹，一直查找字符串的前綴，一直到某個(gè)字母，num為1，即以此為前綴的字符串為1，是唯一的

#include <iostream> #include <stdio.h> #include <cstring> using namespace std;struct Trie {Trie *next[26];int num;Trie(){for (int i = 0; i < 26; i++)next[i] = NULL;num = 0;} };Trie root; void Insert(char *s) {Trie *p = &root;for (int i = 0; s[i]; i++) {int t = s[i]-'a';if (p->next[t] == NULL)p->next[t] = new Trie;p = p->next[t];p->num++;} }void Find(char *s) {Trie *p = &root;for (int i = 0; s[i]; i++) {int t = s[i]-'a';if (p->next[t] == NULL)return;p = p->next[t];printf("%c", s[i]);if (p->num == 1)return;} }int main() {//freopen("1.txt", "r", stdin);int n = 0;char w[1010][21];while (~scanf("%s", w[n])) {Insert(w[n]);n++;}for (int i = 0; i < n; i++) {printf("%s ", w[i]);Find(w[i]);printf("\n");}return 0; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/whileskies/p/7203527.html

總結(jié)

以上是生活随笔為你收集整理的[openjudge] 2797最短前缀 Trie的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。