首页 > 其他分享 >UVA11732 "strcmp()" Anyone?

UVA11732 "strcmp()" Anyone?

时间:2023-08-05 09:04:01浏览次数:55  
标签:子串 UVA11732 前缀 trie 节点 Anyone 索引 字符串 strcmp

UVA11732 "strcmp()" Anyone?

题目传送门

一个我认为比较有趣的问题……

题意

给出 \(n\) 个字符串,两两比较字典序大小,求出所需比较的总次数并输出。

分析

使用 trie 树(字典树)来统计给定字符串集合中所有字符串的前缀子串出现次数之和。

trie 树是一种多叉树数据结构,用于高效地存储和检索字符串集合。每个节点代表一个字符,从根节点开始,通过边上的字符逐层向下遍历,构成一个字符串。

这里的 trie 树是一个特殊的字典树,它的每个节点都有一个整数数组 \(tree\),用于保存子节点的索引。数组的长度是 \(65\),因为这里的字符串包含小写字母、大写字母和数字,共

\[26 + 26 + 10 + 1 + 1 + 1= 65 \]

代码的关键部分是 Insert 函数,它用于将一个字符串插入到 trie 树中,并统计前缀子串出现次数之和。函数具体步骤如下:

从根节点开始,初始化当前节点的索引 \(id\) 为 \(0\),并将全局变量 \(ans\) 初始化为 \(0\),用于记录前缀子串出现次数之和。

将空字符串的计数值加到 \(ans\) 中,表示空字符串是所有字符串的前缀。

依次遍历字符串中的每个字符:

  1. 将字符映射成一个整数 \(c\),用于在 \(tree\) 数组中索引子节点。

  2. 如果当前节点的子节点中不存在字符 \(c\),则创建一个新的子节点,并更新当前节点的索引为新节点的索引,并将该节点计数和结尾计数初始化为 \(0\)。

  3. 更新当前节点的索引 \(id\) 为新的子节点索引。

  4. 将当前节点的计数值加到 \(ans\) 中,表示经过当前节点的前缀子串出现次数,这里加两次是因为前缀出现在当前节点和其所有父节点上。

  5. 更新当前节点的计数值,表示经过该节点的次数。
    遍历完字符串后,更新当前字符串的结尾节点的计数和结尾计数,并将其计数值加到 \(ans\) 中,表示当前字符串在最后一个节点处结束,该节点记录了所有以此字符串结尾的子串出现的次数。

代码的 main 函数中通过循环不断输入字符串,并调用 Insert 函数将字符串插入到 trie 树中。最后输出统计结果。

这样,通过 trie 树的遍历和计数机制,代码可以高效地统计给定字符串集合中所有字符串的前缀子串出现次数之和。

接下来贴上代码。

AC Code

#include<bits/stdc++.h>
using namespace std;
int tree[4000005][65], val[4000005], End[4000005]; // trie树节点信息
int change(char c) // 字符转换函数,将字符映射到整数
{
    if (c >= 'a' && c <= 'z') return c - 'a';     // 映射小写字母a-z到0-25
    if (c >= 'A' && c <= 'Z') return c - 'A' + 26; // 映射大写字母A-Z到26-51
    return c - '0' + 52;                         // 映射数字0-9到52-61
}

int cnt;         // trie树的节点计数
long long ans;   // 统计前缀子串出现次数之和
void Insert(char *s) // 将字符串s插入trie树
{
    int id = 0, l = strlen(s); // id为当前节点索引,l为字符串s的长度
    ans += val[0];             // 统计空字符串的出现次数,即所有字符串的前缀
    val[0]++;                  // 空字符串计数加一
    for (int i = 0; i < l; ++i)
    {
        int c = change(s[i]); // 将字符s[i]转换为整数
        if (!tree[id][c])     // 如果当前节点的子节点不存在
        {
            memset(tree[cnt], 0, sizeof(tree[cnt])); // 初始化子节点信息
            val[cnt] = 0;                            // 子节点计数初始化为0
            End[cnt] = 0;                            // 子节点结尾计数初始化为0
            tree[id][c] = cnt++;                     // 在当前节点创建子节点并更新id为子节点索引
        }
        id = tree[id][c];       // 移动到子节点
        ans += 2LL * val[id];   // 更新统计值,当前节点的计数值加到结果上,每次统计两次,是因为前缀出现在当前节点和当前节点的父节点(父节点的父节点...)上
        val[id]++;              // 更新当前节点的计数值,表示经过当前节点的次数
    }
    ans += End[id]; // 更新统计值,当前字符串在最后一个节点处结束,该节点记录了所有以此字符串结尾的子串出现的次数
    End[id]++;      // 更新该节点的结尾计数值,表示以此字符串结尾的子串出现次数加一
}

void init() // 初始化trie树
{
    cnt = 1;                   // 初始化节点计数为1(根节点已经创建)
    ans = 0;                   // 初始化结果统计为0
    memset(tree[0], 0, sizeof(tree[0])); // 初始化根节点信息
    val[0] = End[0] = 0;       // 根节点计数和结尾计数初始化为0
}

char s[1005]; // 用于存储输入的字符串
int main()
{
    int n, i, ca = 1;
    while (~scanf("%d", &n) && n) // 输入n个字符串进行处理,直到n为0
    {
        init(); // 初始化trie树
        for (i = 0; i < n; ++i)
        {
            scanf("%s", s); // 输入字符串s
            Insert(s);      // 将字符串s插入trie树,并统计前缀子串出现次数之和
        }
        printf("Case %d: %lld\n", ca++, ans); // 输出结果
    }
    return 0;
}

标签:子串,UVA11732,前缀,trie,节点,Anyone,索引,字符串,strcmp
From: https://www.cnblogs.com/cxy-xlf-1003/p/17607449.html

相关文章

  • 104.字符串函数:strlen函数,strcpy函数,strcat函数,strcmp函数
    104.字符串函数:strlen函数,strcpy函数,strcat函数,strcmp函数1.字符串函数strlen(1)strlen函数strlen函数返回的是在字符串中’\0’前面出现的字符的个数(2)strlen的使用a.代码#include<stdio.h>#include<string.h>intmain(){ charstr1[]="abcdef"; printf("%d\n",s......
  • Codeforces Round 882 (Div. 2) C. Vampiric Powers, anyone?
    由题目观察可得,a[m+1]=a[i]^...a[m],,结合异或的性质a^b^a=b,可得如果在末尾添加一个a[m+1],a[m+1]会和末尾几个抵消掉,求得i~k这一段的异或和,k<m,因此通过该操作实际上我就可以求得所有长度连续区间的异或和,求其最大值,n=1e5+10,如果暴力求解肯定会超时,我们观察发现a[i]的范围为0~2^8......
  • strcmp函数
    strcmp函数#include<stdio.h>intmystrcmp(char*a,char*b){while(*a&&*b&&*a==*b){a++;b++;}if((*a-*b)>0){return(*a-*b);}elseif((*a-*b)<0){return(*a-*b);}else{return0;......
  • 模拟实现字符串函数strcat和strcmp
    my_strcat函数实现#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<assert.h>#include<string.h>char*my_strcat(char*dest,constchar*src){ assert(dest&&src); char*ret=dest; //找目标串的'\0' while(*des......
  • strcmp 和 level4 write up
    作业题两题strcmpida打开找到主函数如果答案这么简单就好了尝试在start函数找线索,发现其中的init函数非常可疑该函数访问了地址off_200DF0到funcs_889于是查看了o......
  • strcmp,strcat,strstr模拟实现
    一、strcmp模拟实现1.strcmp原理2.基于其原理进行模拟实现二、strcat模拟实现1.strcat原理2.基于其原理进行模拟实现三、strstr模拟实现1.strstr原理2.基于其......
  • 如何查看库函数实现的某些函数(strlen,strcmp,strcpy等)
    我们拿strlen()作为举例(编译环境为:VS2022)strlen()引用的头文件为string.h,如下进行操作ps:打开strlen.c文件便可以看到库函数对于strlen()的实现,若要搜索其他在库......
  • strcmp函数
    原型:int strcmp(const char *s1, const char *s2);头文件:#include <string.h> 功能:用来比较两个字符串 参数:s1、s2为两个进行比较的字符串 返回值:若s1、s......
  • 相关函数: strcmp
    头文件 :#include<string.h>函数原型:intstrcmp(constchar*s1, constchar*s2);函数说明:比较参数s1和s2所指向的字符串返回值 :若字符串相等则返回0;若字符......
  • buuoj-[Zer0pts2020]easy strcmp
    1.无壳2.打开直奔main函数啊,又是签到题吗?交上去,不对。。。然后开始一顿乱翻这个看起来很可疑查一下谁调用了这个函数,结果又是一顿乱翻,从程序入口找到了这个:一......