字典树水题几枚

2023-11-08 09:32
文章标签 字典 树水题 几枚

本文主要是介绍字典树水题几枚，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.HDU 1251 统计难题

很裸的一道字典树，直接输出个数的， 其实用map也能水过，只不过效率有些低

map版本

map做法就是把每个字符串的所有前缀遍历一遍，然后存起来，最后直接数个数就行。

具体代码吐下  很久很久以前的代码  很挫

#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
char s[11];
int main()
{map<string,int>mp;int i;while(gets(s)){int len=strlen(s);if(!len)break;string a="";for(i=0;i<len;i++){a=a+s[i];mp[a]++;}}char ss[11];while(scanf("%s",ss)!=EOF){string tmp=ss;printf("%d\n",mp[tmp]);}return 0;
}


然后是字典树版本的， 刚写的，略挫 

/*
ID: sdj22251
PROG: calfflac
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define INF 100000000
#define PI acos(-1.0)
using namespace std;
char str[12];
struct trie
{int num;trie *next[26];trie(){num = 0;for(int i = 0; i < 26; i++)next[i] = 0;}
} *root, temp[500005]; // 为了避免用new太多浪费时间，事先开好一个数组， 当然，内存又有可能爆掉了
int ncount = 0;
void insert(trie *p, char *s)
{int ix = 0;p ->num++;while(s[ix]){int nx = s[ix] - 'a';if(p -> next[nx]){p = p -> next[nx];ix++;}else{p -> next[nx] = &temp[ncount++]; //直接取址p = p -> next[nx];ix++;}p -> num++;}
}
int find(trie *p, char *s)
{int ix = 0, ans;while(s[ix]){int nx = s[ix] - 'a';if(p -> next[nx]){p = p -> next[nx];ans = p -> num;ix++;}else return 0;}return ans;
}
int main()
{//freopen("ride.in","r",stdin);//freopen("ride.out","w",stdout);root = new trie;while(gets(str)){if(strlen(str) == 0) break;insert(root, str);}while(scanf("%s", str) != EOF){printf("%d\n", find(root, str));}return 0;
}
 

2.POJ 2001 Shortest Prefixes

同样，很裸的字典树。

/*
ID: sdj22251
PROG: calfflac
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAX 100000000
#define PI acos(-1.0)
using namespace std;
char s[1005][23];
struct trie
{int num;trie *next[26];trie(){num = 0;for(int i = 0; i < 26; i++)next[i] = NULL;}
}*root, temp[50000];
int ncount = 0;
void insert(trie *p, char *s)
{int ix = 0;p -> num++;while(s[ix]){int nx = s[ix] - 'a';if(p -> next[nx]){p = p -> next[nx];ix++;}else{p -> next[nx] = &temp[ncount++]; //直接取址p = p -> next[nx];ix++;}p -> num++;}
}
int find(trie *p, char *s)
{int ix = 0, ans;while(s[ix]){int nx = s[ix] - 'a';if(p -> next[nx]){p = p -> next[nx];ans = p -> num;ix++;}else return 0;}return ans;
}
int main()
{//freopen("ride.in","r",stdin);//freopen("ride.out","w",stdout);int cnt = 0, i, j;root = new trie;while(scanf("%s", s[cnt++]) != EOF){insert(root, s[cnt - 1]);}for(i = 0; i < cnt; i++){int len = strlen(s[i]);char tp[23];for(j = 0; j < 21; j++)tp[j] = '\0';int ct = 0;for(j = 0; j < len; j++){tp[ct++] = s[i][j];if(find(root, tp) == 1){break;}}printf("%s %s\n", s[i], tp);}return 0;
}


3. HDU 1247  


这个就当做模板吧。。。 

字典树应用，先插入所有单词，然后暴力拆分每个单词，看拆分后的两个单词是否都在字典树中出现，注意是确切出现，而不是作为子串出现，所以插入的时候注意下

/*
ID: CUGB-wwj
PROG:
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define INF 100000000
#define PI acos(-1.0)
using namespace std;
char str[50051][50];
struct trie
{int num;trie *next[26];trie(){num = 0;for(int i = 0; i < 26; i++)next[i] = NULL;}
} *root ;
int ncount = 0;
void insert(trie *p, char *s)
{int ix = 0;while(s[ix]){int nx = s[ix] - 'a';if(p -> next[nx] == NULL)p -> next[nx] = new trie();p = p -> next[nx];ix++;}p -> num++;
}
int find(trie *p, char *s)
{int ix = 0, ans = 0;while(s[ix]){int nx = s[ix] - 'a';if(p -> next[nx]){p = p -> next[nx];ans = p -> num;ix++;}else return 0;}return ans;
}
int main()
{root = new trie();while(scanf("%s", str[ncount++]) != EOF){insert(root, str[ncount - 1]);}for(int i = 0; i < ncount; i++){int len = strlen(str[i]);int flag = 0;for(int j = 1; j < len; j++){char ta[22], tb[22];memset(ta, '\0', sizeof(ta));memset(tb, '\0', sizeof(tb));int cnt1 = 0, cnt2 = 0;for(int k = 0; k < j; k++)ta[cnt1++] = str[i][k];for(int k = j; k < len; k++)tb[cnt2++] = str[i][k];if(find(root, ta) && find(root, tb)){flag = 1;break;}}if(flag) puts(str[i]);}return 0;
}


这篇关于字典树水题几枚的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/369027。

相关文章

POJ2001字典树

POJ2001字典树

给出n个单词，求出每个单词的非公共前缀，如果没有，则输出自己。 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.io.UnsupportedEncodingException;
阅读更多...
python 实现第k个字典排列算法

python 实现第k个字典排列算法

第k个字典排列算法介绍 "第k个字典排列"算法通常指的是在给定的字符集合（例如，字符串中的字符）中，找到所有可能排列的第k个排列。这个问题可以通过多种方法解决，但一个常见且高效的方法是使用“下一个排列”算法的变种，或称为“第k个排列”的直接算法。 方法一：使用“下一个排列”的变种 生成所有排列：首先生成所有排列，但显然这种方法对于较大的输入集合是不切实际的，因为它涉及到大量的计算和存储。 排序
阅读更多...
POJ3617(字典序最小问题)

POJ3617(字典序最小问题)

书中43页 此题有坑点，PE了40分钟.也是醉了....题目要求每80个字符才换行，而且最后一个如果恰好就不用换，这不是无聊嘛....... #include <iostream>#include <cstdio>#include <cstring>using namespace std;int n,m;char S[2100],P[2100];int main(){#ifd
阅读更多...
POJ 2001 Shortest Prefixes（字典树入门）

POJ 2001 Shortest Prefixes（字典树入门）

题目： http://poj.org/problem?id=2001 题意： 找到多个字符串中，各自唯一的最短子串，例如 carte 与 carce 各自唯一的最短子串为cart与carc，即不会与其它字符串的子串重复。 思路: 字典树 解题心得: 更新关键值的时机很重要 代码： #include<stdio.h>#include<string>typedef str
阅读更多...
Oracle数据库（数据字典、表空间、表的创建、视图）

Oracle数据库（数据字典、表空间、表的创建、视图）

知识点引用： http://www.2cto.com/database/201207/142874.html http://blog.csdn.net/haiross/article/details/11772847 一. 彻底卸载Oracle 方式1、重装操作系统 方式2、 2.1 DBCA删除数据库开始 → 程序 → Oracle → 开发与移植工具 → Datab
阅读更多...
Python的字符串，list，tuple，set，字典操作详解

Python的字符串，list，tuple，set，字典操作详解

1.字符串python是要创建成字符串的元素，其中的每个字母都是单一的子串，把它放在' '单引号或是'' ''引号中，就完成了python 字符串的创建。#str强制转换>>> a=123>>> b=str(a) #将整数转化为字符串>>> b'123'>>> a=[1,2,3]>>> b=str(a) #将list转化为字符串>>> b'[1, 2, 3]'#字符串下
阅读更多...
OC中数组、字典、集合常用方法的运用

OC中数组、字典、集合常用方法的运用

/* ====================== 一 NSArray========================          1.创建对象          1.1初始化方法(2) //一般程序有问题先检查初始化          1.2类方法          1.3字面量方法          2.数组查找          2.1通过下标访问对象[ .[i]]
阅读更多...
python pickle 模块用于保存python内存数据（包括实例对象、字典、列表等所有python中的数据）

python pickle 模块用于保存python内存数据（包括实例对象、字典、列表等所有python中的数据）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档 文章目录 前言基本用法 前言 Python 的 pickle 模块用于序列化和反序列化 Python 对象。这意味着你可以将 Python 对象（如列表、字典、类实例等）转换为字节流（序列化），并将其保存到文件中或在网络上传输，然后在需要的时候将其恢复为原始 Python 对象（反序列化）。 常见用途
阅读更多...
Python 从入门到实战8（字典）

Python 从入门到实战8（字典）

我们的目标是：通过这一套资料学习下来，通过熟练掌握python基础，然后结合经典实例、实践相结合，使我们完全掌握python，并做到独立完成项目开发的能力。       上篇文章我们通过举例学习了python 中元组的定义及相关操作。今天详细讲述字典的定义及相关的操作，也是经常使用到的。 1、字典的定义 字典是由{}括住的，内容以“键-值对”的形式存储的无序序列。 字典的主要特点如下：
阅读更多...
Python 字典详解

Python 字典详解

Python 字典 : 字典是另一种可变容器模型，且可存储任意类型对象。 字典的每个键值(key=>value)对用冒号(:)分割，每个对之间用逗号(,)分割，整个字典包括在花括号({})中 ,格式如下所示： d = {key1 : value1, key2 : value2 } 键必须是唯一的，但值则不必。 值可以取任何数据类型，但键必须是不可变的，如字符串，数字或元组。 一个简单的
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2