当前位置:网站首页>UVa 11732 – strcmp() Anyone?
UVa 11732 – strcmp() Anyone?
2022-07-06 22:33:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack .
The title of : Here's something for you , Give you a string comparison function , All words are parity , What is the number of comparisons .
analysis : string 、 terry .
First . Look at the data size , Suppose you find clues normally , meeting TLE and MLE.
because , The conventional dictionary tree depth is 1000, And there may be a lot of waste of correction space .
therefore , Adopt the compression algorithm of tree ( Brother left , The right child ). Can improve execution efficiency .
then . The same level in the dictionary tree can . In Statistics , Be able to make achievements before making statistics , Or make statistics while building trees .
Here I choose the method of statistics while building trees ( A large number of online practices , They are built first and then counted , Search for solutions )
Every time you insert a word . It is only compared with the words inserted before ; The comparison times of words are the sum of the comparison times of each letter .
The number of comparisons of each letter in a word . It is the number of words included in the root node of this letter .
Word comparison functions such as the following :
int strcmp(char *s, char *t)
{
int i;
for (i=0; s[i]==t[i]; i++)
if (s[i]=='\0')
return 0;
return s[i] - t[i];
}
Because the comparison function is as above , Pay attention to the following points when calculating :
1. The same length is L The cost of comparing two words of is 2L-1. Go out for the last time s Concluded inference ;
2. The comparative length of words should be strlen(str)+1, The terminator is also a part of comparison ;
3. Suppose two words are the same , Then calculate one more time to end the inference . Comparison times +1.
Be careful : Use LL, Otherwise the data will overflow .
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
char words[1010];
/* Trie define */
#define nodesize 4444444 // Number of nodes
typedef struct node1
{
char value;
int size;
int count;
node1* Lchild;
node1* Rchild;
}tnode;
tnode dict[nodesize];
class Trie
{
private:
LL count;
int size;
tnode* root;
public:
Trie() {initial();}
void initial() {
memset( dict, 0, sizeof(dict) );
size=0;count=0LL;root=newnode(0);
}
tnode* newnode( char c ) {
dict[size].value = c;
return &dict[size ++];
}
void insert( char* word, int L ) {
tnode* now = root->Rchild,*save = root;
int same = 1;
for ( int i = 0 ; i <= L ; ++ i ) {
if ( !now ) {
save->Rchild = newnode(word[i]);
now = save->Rchild;
now->count = 1;
same = 0;
}else {
if ( i ) count += now->count;
count += now->count ++;
while ( now->Lchild && now->value != word[i] )
now = now->Lchild;
if ( now->value != word[i] ) {
now->Lchild = newnode(word[i]);
now = now->Lchild;
same = 0;
}
}
save = now;
now = save->Rchild;
}
if ( same ) save->size ++;
count += save->size;
}
LL query() {return count;}
}trie;
/* Trie end */
int main()
{
int Case = 1,N;
while ( scanf("%d",&N) != EOF ) {
if ( !N ) break;
trie.initial();
for ( int i = 0 ; i < N ; ++ i ) {
scanf("%s",words);
trie.insert(words,strlen(words));
}
printf("Case %d: %lld\n",Case ++,trie.query());
}
return 0;
}
Copyright notice : This article is the original article of the blogger . Blog , Do not reprint without permission .
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/116985.html Link to the original text :https://javaforall.cn
边栏推荐
- pytorch_YOLOX剪枝【附代码】
- 【踩坑合辑】Attempting to deserialize object on CUDA device+buff/cache占用过高+pad_sequence
- three.js绚烂的气泡效果
- 视图(view)
- [linear algebra] determinant of order 1.3 n
- MySQL----初识MySQL
- Mise en place d'un environnement de développement OP - tee basé sur qemuv8
- 2022-07-05 stonedb的子查询处理解析耗时分析
- poj 1094 Sorting It All Out (拓扑排序)
- 做接口测试都测什么?有哪些通用测试点?
猜你喜欢
机试刷题1
基于 QEMUv8 搭建 OP-TEE 开发环境
Crawler obtains real estate data
Signed and unsigned keywords
C# 三种方式实现Socket数据接收
leetcode:面试题 17.24. 子矩阵最大累加和(待研究)
软考高级(信息系统项目管理师)高频考点:项目质量管理
Adavit -- dynamic network with adaptive selection of computing structure
signed、unsigned关键字
The SQL response is slow. What are your troubleshooting ideas?
随机推荐
pytorch_ Yolox pruning [with code]
2022-07-05 stonedb的子查询处理解析耗时分析
Jafka来源分析——Processor
0 basic learning C language - interrupt
Windows Auzre 微软的云计算产品的后台操作界面
config:invalid signature 解决办法和问题排查详解
做接口测试都测什么?有哪些通用测试点?
Leetcode question brushing (XI) -- sequential questions brushing 51 to 55
BasicVSR_PlusPlus-master测试视频、图片
树的先序中序后序遍历
Aardio - 封装库时批量处理属性与回调函数的方法
MySQL----初识MySQL
UVa 11732 – strcmp() Anyone?
Daily question 1: force deduction: 225: realize stack with queue
How do I write Flask's excellent debug log message to a file in production?
return 关键字
The ceiling of MySQL tutorial. Collect it and take your time
Plafond du tutoriel MySQL, bien collecté, regardez lentement
柔性数组到底如何使用呢?
第4章:再谈类的加载器