UVA11732 strcmp() Anyone?(Trie树)

strcmp() Anyone? Time Limit:2000MS     Memory Limit:0KB     64bit IO Format:%lld & %llu
Submit Status Practice UVA 11732
Appoint description:

Description

J

“strcmp()” Anyone?

Input: Standard Input

Output: Standard Output

 

strcmp() is a library function in C/C++ which compares two strings. It takes two strings as input parameter and decides which one is lexicographically larger or smaller: If the first string is greater then it returns a positive value, if the second string is greater it returns a negative value and if two strings are equal it returns a zero. The code that is used to compare two strings in C/C++ library is shown below:

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];
}

Figure: The standard strcmp() code provided for this problem.

 

The number of comparisons required to compare two strings in strcmp() function is never returned by the function. But for this problem you will have to do just that at a larger scale. strcmp() function continues to compare characters in the same position of the two strings until two different characters are found or both strings come to an end. Of course it assumes that last character of a string is a null (‘\0’) character. For example the table below shows what happens when “than” and “that”; “therE” and “the” are compared using strcmp() function. To understand how 7 comparisons are needed in both cases please consult the code block given above.

 

t

h

a

N

\0

 

t

h

e

r

E

\0

 

=

=

=

 

=

=

=

 

 

t

h

a

T

\0

t

h

e

\0

 

 

Returns negative value

7 Comparisons

Returns positive value

7 Comparisons

 

Input

The input file contains maximum 10 sets of inputs. The description of each set is given below:

 

Each set starts with an integer N (0<N<4001) which denotes the total number of strings. Each of the next N lines contains one string. Strings contain only alphanumerals (‘0’… ‘9’, ‘A’… ‘Z’, ‘a’… ‘z’) have a maximum length of 1000, and a minimum length of 1.  

 

Input is terminated by a line containing a single zero. Input file size is around 23 MB.

 

Output

For each set of input produce one line of output. This line contains the serial of output followed by an integer T. This T denotes the total number of comparisons that are required in the strcmp() function if all the strings are compared with one another exactly once. So for N strings the function strcmp() will be called exactly  times. You have to calculate total number of comparisons inside the strcmp() function in those  calls. You can assume that the value of T will fit safely in a 64-bit signed integer. Please note that the most straightforward solution (Worst Case Complexity O(N2 *1000)) will time out for this problem.

 

Sample Input                              Output for Sample Input

2

a

b

4

cat

hat

mat

sir

0

Case 1: 1

Case 2: 6

 


字符串很多,数据量很大,两两比较肯定超时,如果把所有的单词加入到一棵Trie树,然后比较就只需要比较
树出现分叉的地方并且获得那个地方节点的权值,比如
than 和that比较,首先加入Trie树,如图所示


than和that的前三个字符相同,第四个不同,因此比较次数为7,即n(n-1)/2次

// UVa11732 strcmp() Anyone?
// Rujia Liu
#include<cstring>
#include<vector>
#include<cstdio>
using namespace std;
#define LL long long
const int maxnode = 4000 * 1000 + 10;
const int sigma_size = 26;
int head[maxnode]; /// head[i]为第i个结点的左儿子编号
int next[maxnode]; /// next[i]为第i个结点的右兄弟编号
char ch[maxnode];  /// ch[i]为第i个结点上的字符
int tot[maxnode];  /// tot[i]为第i个结点为根的子树包含的叶结点总数
int flag[maxnode];
int sz;/// 结点总数
LL ans;
void insert(const char *s)
{
    ans+=tot[0]; /// 答案
    tot[0]++;
    //sz = 1;    /// 初始时只有一个根结点

    int u = 0, v, n = strlen(s);
    int k;
/// 插入字符串s(包括最后的'\0'),沿途更新tot

    for(int i = 0; i < n; i++)
    {
        ///找字符a[i]
        bool found = false;
        for(v = head[u]; v != 0; v = next[v])
            if(ch[v] == s[i])   /// 找到了
            {
                found = true;
                break;
            }
        if(!found)
        {
            v = sz++; /// 新建结点
            tot[v] = 0;
            flag[v]=0;
            ch[v] = s[i];
            next[v] = head[u];
            head[u] = v; /// 插入到链表的首部
            head[v] = 0;
        }
        u = v;
        ans+=tot[u]*2;
        tot[u]++;
    }
    k=v;
/// 统计LCP=u的所有单词两两的比较次数之和

    if(flag[k])
        ans+=flag[k];
    flag[k]++;
}


const int maxl = 1000 + 10;/// 每个单词最大长度
int n;
char word[maxl];
int main()
{
    int kase = 1;
    while(scanf("%d", &n) == 1 && n)
    {
        //trie.clear();
        ans=0,sz=1;
        tot[0] = head[0] = next[0] = 0;
        for(int i = 0; i < n; i++)
        {
            scanf("%s", word);
            insert(word);
        }
        printf("Case %d: %lld\n", kase++, ans);
    }
    return 0;
}



版权声明:本文为qq_32792879原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_32792879/article/details/76021823

智能推荐

Ubuntu 14.04 下,安装 Java8

下载Java http://www.oracle.com/technetwork/java/javase/downloads/jdk8-downloads-2133151.html 打开上述链接, , 下载 特定的 Java8 版本。笔者选择的是 jdk-8u172-linux-x64.tar.gz。 - 配置Java环境变量 将 jdk-8u172-linux-x64.tar.gz 解压至指定目...

OpenCV学习之路(五)图像的几何变换

在这一章将要学习图像的移动、旋转,仿射变换等 扩展缩放 我们如果想要改变图像的大小,我们就需要对图像进行扩展缩放,opencv提供给我们控制扩展缩放的函数: 参数解释: src:进行扩展缩放的原图片 dst:可以在此处设置缩放因子,也可手动设置尺寸 interpolation:在缩放时我们推荐使用cv2.INTER_AREA, 在扩展时我们推荐使用cv2.INTER_CUBIC(慢) 和 cv2....

2018.8.27

2018.8.27...

HTML 表单元素的基本样式

HTML 表单元素的基本样式 原创 ixygj197875 发布于2018-02-22 17:48:53 阅读数 2296 收藏 更新于2018-05-20 15:35:58 分类专栏: 揭秘 CSS 揭秘 CSS 收起 表单元素主要包括 label、input、textarea、select、datalist、******、progress、meter、output等,以及对表单元素进行分组的 ...

php输出语句

php输出语句 常见的输出语句 echo(): 可以一次输出多个值,多个值之间用逗号分隔。echo是语言结构(language construct),而并不是真正的函数,因此不能作为表达式的一部分使用。 print(): 函数print()打印一个值(它的参数),如果字符串成功显示则返回true,否则返回false。 print_r(): 可以把字符串和数字简单地打印出来,而数组则以括起来的键和值...

猜你喜欢

工厂模式

简介 常见的实例化对象模式。 用工厂方法替代new操作的一种模式。 当我们使用new操作实例化对象时,调用构造函数完成初始化。若初始化仅是进行赋值等简单的操作,写入构造函数即可。但如果初始化时需要执行一长串复杂的代码,将多个工作装入一个方法,是不妥的。 创建实例与使用实例分离。将创建实例所需的大量初始化工作从基类的构造函数中分离出去。 简单工厂模式、工厂方法模式针对的是一个产品等级结构;而抽象工厂...

B1105 Spiral Matrix (画图)

B1105 Spiral Matrix (25分) //第一次只拿了21分 矩阵的长和宽,求最大因子,从sqrt(num)开始枚举. 每次循环一次,s++,t--,d--,r++ 测试点四运行超时,是因为输入一个数字的时候,需要直接输出这个数字。//1分 测试点二运行超时,最后一个数字不必再while循环一次,直接输出即可。//3分 最后一个测试点卡了好久/(ㄒoㄒ)/~~ 螺旋矩阵...

Java基础=>String,StringBuffer与StringBuilder的区别

字符串常量池 什么是字符串常量池? JVM为了减少字符串对象的重复创建,其维护了一块特殊的内存,这段内存被称为字符串常量池(存储在方法区中)。 具体实现 当代码中出现字符串时,JVM首先会对其进行检查。 如果字符串常量池中存在相同内容的字符串对象,如果有,则不再创建,直接返回这个对象的地址返回。 如果字符串常量池中不存在相同内容的字符串对象,则创建一个新的字符串对象并放入常量池,并返回新创建的字符...

java调用其他java项目的Https接口

项目中是这样的: 用户拿出二维码展示,让机器识别二维码, 机器调用开门的后台系统接口, 然后开门的后台系统接口需要调用管理系统的接口, 管理系统需要判断能不能开门.这两个系统是互相独立的.当时使用http调用是没有问题的.当时后来要求必须用https.废话不说,直接代码: 我的项目中调用的是 HttpsUtils.Get(utlStr) 这个接口 开门系统接口如下图:   管理系统的接口...

Hadoop1.2.1全分布式模式配置

一 集群规划 主机名            IP                               安装的软件 &nbs...