当前位置:网站首页>UVa 11732 – strcmp() Anyone?
UVa 11732 – strcmp() Anyone?
2022-07-06 15:10:00 【全栈程序员站长】
大家好,又见面了,我是全栈君。
称号:给你一些话,给你一个字符串比较函数,所有的话都当奇偶校验,什么是比较次数。
分析:弦、特里。
首先。看数据大小,假设正常的发现线索,会议TLE和MLE。
由于,常规的字典树深度为1000,并且有可能会有大量的指正空间浪费。
所以,採用树的压缩算法(左兄弟,右孩子)。能够提高执行效率。
然后。在字典树上同级就可以。统计时,能够先建树再统计,或者边建树边统计。
这里我选用边建树边统计的方法(网上大量的做法,都是先建树再统计的,搜索求解)
每次插入单词时。它仅仅与前面插入的单词比較;单词的比較次数为当中每一个字母的比較次数的和。
单词中每一个字母的比較次数。就是这个字母的根节点包括的单词个数。
单词比較函数例如以下:
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];
}
由于比較函数如上,计算时要注意下面几点:
1.同样长度为L的两个单词比較代价为2L-1。出最后一次外要进行s结束的推断;
2.单词的比較长度应该为strlen(str)+1,结束符也是比較的一环;
3.假设两个单词同样,则多计算一次结束推断。比較次数+1。
注意:使用LL,否则数据会溢出。
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
char words[1010];
/* Trie define */
#define nodesize 4444444 //节点个数
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;
}
版权声明:本文博主原创文章。博客,未经同意不得转载。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116985.html原文链接:https://javaforall.cn
边栏推荐
- 2500 common Chinese characters + 130 common Chinese and English characters
- case 关键字后面的值有什么要求吗?
- 自制J-Flash烧录工具——Qt调用jlinkARM.dll方式
- 2022-07-05 stonedb的子查询处理解析耗时分析
- 枚举与#define 宏的区别
- Unity3d Learning Notes 6 - GPU instantiation (1)
- 雅思口语的具体步骤和时间安排是什么样的?
- labelimg的安装与使用
- [sdx62] wcn685x will bdwlan Bin and bdwlan Txt mutual conversion operation method
- SQL Server生成自增序号
猜你喜欢
2022-07-04 mysql的高性能数据库引擎stonedb在centos7.9编译及运行
2022-07-04 the high-performance database engine stonedb of MySQL is compiled and run in centos7.9
在IPv6中 链路本地地址的优势
Chapter 4: talk about class loader again
[线性代数] 1.3 n阶行列式
ResNet-RS:谷歌领衔调优ResNet,性能全面超越EfficientNet系列 | 2021 arxiv
【数字IC手撕代码】Verilog无毛刺时钟切换电路|题目|原理|设计|仿真
Should novice programmers memorize code?
Assembly and interface technology experiment 5-8259 interrupt experiment
Advantages of link local address in IPv6
随机推荐
中国1,4-环己烷二甲醇(CHDM)行业调研与投资决策报告(2022版)
Anaconda installs third-party packages
AdaViT——自适应选择计算结构的动态网络
Assembly and Interface Technology Experiment 6 - ADDA conversion experiment, AD acquisition system in interrupt mode
3DMAX assign face map
柔性数组到底如何使用呢?
2022-07-05 stonedb的子查询处理解析耗时分析
【编译原理】做了一半的LR(0)分析器
MySQL数据库基本操作-DML
做国外LEAD2022年下半年几点建议
Management background --3, modify classification
0 basic learning C language - interrupt
2022-07-05 使用tpcc对stonedb进行子查询测试
Clip +json parsing converts the sound in the video into text
config:invalid signature 解决办法和问题排查详解
Advantages of link local address in IPv6
NPDP certification | how do product managers communicate across functions / teams?
【踩坑合辑】Attempting to deserialize object on CUDA device+buff/cache占用过高+pad_sequence
Crawler obtains real estate data
【雅思口语】安娜口语学习记录part1