题目
一个文件里面有如下字符串
cartefdxh
cart
carlkijfwe
chdfwef
cafkekfld
…………
要从文件中找出唯一能代表该字符串的前缀,然后如下输出
cartefdxh carte
cart cart
carlkijfwe carl
chdfwef ch
cafkekfld caf
以空格分隔…….
思路
用Trie树实现。为每个节点增加一个变量count,用来记录一共有几个字符串使用该字符。找节点计数为1的节点或者叶子节点。
代码
#include <iostream>
#include <vector>
using namespace std;
#define MAX 26
struct TrieNode{
int count;
TrieNode *next[MAX];
TrieNode(){
count = 0;
for(int i = 0;i < MAX;++i){
next[i] = NULL;
}
}
};
void Insert(TrieNode* &root,string str){
int size = str.size();
if(size == 0){
return;
}
TrieNode *p = root;
int val;
for(int i = 0;i < size;++i){
val = str[i] - 'a';
if(p->next[val] == NULL){
p->next[val] = new TrieNode();
}
p->next[val]->count++;
p = p->next[val];
}
}
string OnlyPrefix(TrieNode* root,string str){
int size = str.size();
TrieNode *p = root;
int index = 0,val;
for(int i = 0;i < size;++i){
val = str[i] - 'a';
index++;
p = p->next[val];
if(p->count == 1){
break;
}
}
return str.substr(0,index);
}
vector<pair<string,string> > AllOnlyPrefix(vector<string> strs){
int size = strs.size();
pair<string,string> prefix;
vector<pair<string,string> > vec;
if(size <= 0){
return vec;
}
TrieNode *root = new TrieNode();
for(int i = 0;i < size;++i){
Insert(root,strs[i]);
}
for(int i = 0;i < size;++i){
prefix.first = strs[i];
prefix.second = OnlyPrefix(root,strs[i]);
vec.push_back(prefix);
}
return vec;
}
int main() {
vector<string> strs = {"book","boom","cartefdxh","cart","carlkijfwe","chdfwef","cafkekfld"};
vector<pair<string,string> > vec = AllOnlyPrefix(strs);
for(int i = 0;i < vec.size();++i){
pair<string,string> pair = vec[i];
cout<<pair.first<<" "<<pair.second<<endl;
}
}
引用:
[算法系列之二十]字典树(Trie)
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
字典树求具有公共前缀的字符串数目, 对应的博客地址:http://blog.csdn.net/ns_code/article/details/21183495
树 * 字典树 * 遍历-层次遍历 * 遍历-中序遍历-非递归 * 遍历-前序遍历-非递归 * 遍历-后序遍历-非递归 * 二叉查找树-两数之和 ...数组&字符串 查找排序 排列组合 动态规划 树 链表 数学 位运算 编程之美
字典序问题:在数据加密和数据压缩中常需要对特殊的字符串进行编码。给定的字母表 A 由 26 个小 写英文字母组成 A={a,b,…,z}。该字母表产生的升序字符串是指字符串中字母按照从左到 右出现的次序与字母在字母表中...
有时,我们会碰到对字符串的排序,若采用一些经典的排序算法,则时间复杂度一般为O(n*lgn),但若采用Trie树,则时间复杂度仅为O(n)
格式化字符串的时候用到字典。原文:学学Python_字符串07_字典的格式化字符串
编写程序从某个文本文件中读入若干个字符串(文本文件中每行一个字符串,每个字符串长度不超过80个字符),将字符串按字典序(从小到大)排序,结果输出到另一个文本文件中。要求此程序能处理任意多个字符串。
从键盘输入10个字符串到一个字符串数组中,按字典顺序对各字符串排序
现在对字母表A 产生的所有长度不超过6 的升序字符串按照字典序排列并编码如下。 1 2 … 26 27 28 … 对应 a b … z ab ac … 对于任意长度不超过6 的升序字符串,迅速计算出它在上述字典中的编码。 编程任务: ...
字符串处理——字典树.rar
算法训练 比较字符串 时间限制:1.0s 内存限制:512.0MB 编程实现两个字符串s1和s2的字典序比较。若它们不相等,则指出其第一个不同字
按字典顺序比较两个字符串。该比较基于字符串中各个字符的 Unicode 值。将此 String 对象表示的字符序列与参数字符串所表示的字符序列进行比较。如果按字典顺序此 String 对象在参数字符串之前,则比较结果为一个负...
把NSDictionary类型的数据转换为json,这个目前没找到ios自带方法,引用了...//dic就是你将要转换成字典,而returnString就是齐刷刷的json数据了 当然得导入头文件 #import "JSONKit.h" ok,大功告成,功能以基本实现。
字符串字典序排序软件,最简单的程序,可以用升序和降序两种方式输出。
运行程序之后输入任意的字符串,将字符串转化成二进制数字字符串,然后利用LZ78算法实现对二进制字符串压缩解压,最后再恢复原来的字符串
用来进行字符串的匹配,结合了字典树等算法,提高了时间复杂度
python字符串, 列表, 字典, 集合方法说明
还一一些比如用于比较两个变量是否引用同一个对象、equals用于比较两个字符串的内容是否相同、忽略大小写、判断是否以某个字符串开始或结束、根据字典排序比较两个字符串、删除字符串中的空格、将字符串转换成小写或...
对于给定一个字符串的编号,迅速解码出它在上述字典中的字符串编码。 数据输入 输入数据由input.txt提供。文件的第一行为一个整数N (1,000),表示字符串 的编号。 数据输出 输出该编号做对应的字符串编码到ouput.txt...
C语言程序设计-对长度为8个字符的字符串,将8个字符按降序排列;例如:原来的字符串为CEAedcab,排序后输出为edcbaE