发布于 由itewqq

[训练指南][字典树][简单] strcmp的比较次数 UVa11732

题目给了strcmp()的代码，然后问给出n个串两两之间strcmp总共会用到多少次==操作。建立一棵字典树，节点信息存储一个前缀之前出现的次数即可，另外还需要存储的信息是当前节点 是多少个串的结束点（这样就不用把’\n’也加入树了）

坑点的话，自己wa的原因是没有看到他大小写数字都可以有TAT我用我的只考虑了小写字母的Trie送了好几发wa（貌似每次这种题出错都是这样？

#include 
#include 
#include 
#include
#include
#include
#include
#include
#include
//#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn=1e3+5;
const int MOD=20071027;
const int maxnode=4005*1000+5;
const int csize=70;

char st[maxn];
int d[maxn];
//int n;

int ch[maxnode][csize];
int val[maxnode],ed[maxnode];
int sz;
int idx(char c)//fuck!
{
    if(isdigit(c))
        return c-'0';
    if(islower(c))
        return c-'a'+10;
    if(isupper(c))
        return c-'A'+40;
}

void clear()
{
    sz=1;
    memset(ch[0],0,sizeof(ch[0]));
    memset(val,0,sizeof(val));
    memset(ed,0,sizeof(ed));
}

void insert(char *s,LL &sum)
{
    int flag=0;
    int u=0,n=strlen(s);
    for (int i=0; i

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

此站点使用 Akismet 来减少垃圾评论。了解我们如何处理您的评论数据。