UVa 11732 – strcmp() Anyone?

UVa 11732 – strcmp() Anyone?

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

称号:给你一些话,给你一个字符串比较函数,所有的话都当奇偶校验,什么是比较次数。

分析:弦、特里。

首先。看数据大小,假设正常的发现线索,会议TLE和MLE。

            由于,常规的字典树深度为1000,并且有可能会有大量的指正空间浪费。

            所以,採用树的压缩算法(左兄弟,右孩子)。能够提高执行效率。

            然后。在字典树上同级就可以。统计时,能够先建树再统计,或者边建树边统计。

            这里我选用边建树边统计的方法(网上大量的做法,都是先建树再统计的,搜索求解)

            每次插入单词时。它仅仅与前面插入的单词比較;单词的比較次数为当中每一个字母的比較次数的和。

            单词中每一个字母的比較次数。就是这个字母的根节点包括的单词个数。

            单词比較函数例如以下:

int strcmp(char *s, char *t)
{
    int i;
    for (i=0; s[i]==t[i]; i++)
        if (s[i]=='
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];
}
') 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;
}

版权声明:本文博主原创文章。博客,未经同意不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116985.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • LINUX安装nginx详细步骤「建议收藏」

    1.安装依赖包//一键安装上面四个依赖yum-yinstallgcczlibzlib-develpcre-developensslopenssl-devel2.下载并解压安装包//创建一个文件夹cd/usr/localmkdirnginxcdnginx//下载tar包wgethttp://nginx.org/download/nginx-1.13…

  • javaweb-spring-52

    javaweb-spring-52

  • android 抛出FileNotFoundException异常

    android 抛出FileNotFoundException异常大家都知道,Android6.0中,某些权限属于ProtectedPermission,例如:读写手机存储权限,仅仅在AndroidManifest.xml中申明是无法真正获取到权限的,打开手机的权限管理页面,我们可以看见,读写手机存储权限栏是一个问号,这意味着App并未获取到该权限。这是访问手机存储时,会报出类似下面的错误:java.io.FileNotFoundExcept…

    2022年10月30日
  • python 404_python检测404页面

    python 404_python检测404页面某些网站为了实现友好的用户交互,提供了一种自定义的错误页面,而不是显示一个大大的404,比如CSDN上的404提示页面如下:这样虽然提高了用户体验,但是在编写对应POC进行检测的时候如果只根据返回的HTTP头部信息判断,则很可能造成误报,为了能准确检测到404页面,需要从状态码和页面内容两个方面来进行判断。从状态码来判断比较简单。可以直接使用requests库发送http请求,得到响应码即可。从…

  • 卡盟主站安装教程

    卡盟主站安装教程config.php数据库连接文件配置 视频密码confighttp://www.tudou.com/v/adVnUX3dMOM/&amp;rpid=61582914&amp;resourceId=61582914_04_05_99/v.swf卡盟主站搭建源码上传 视频密码kamengyuanmahttp://www.tudou.com/v/yv0tpzikiC8/&amp;rp…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号