一些代码字典树.pdfVIP

HDU3724给你一堆字符串和一堆条形码，条形码长度分两种，有宽的和窄的，宽的是窄的

两倍，但有0.95-1.05倍的误差，宽的代表1，窄的代表0，对应二进制后转10进制得到ASCII

码，然后匹配原先给的一堆字符串，问有多少个这样的前缀。

字典树，0.95-1.05的误差可以这样，找出最大，然后除以0.95，尽可能放大，然后除以其

他的数，那些数除的时候分别自己除以1.05，尽可能缩小，这样要是大于两倍就可以判断了。

#define_CRT_SECURE_NO_WARNINGS

#includeiostream

#includestring

#includecstring

#includecstdio

#includecmath

#includevector

#includeset

#includealgorithm

#includeiomanip

#includequeue

#includestack

#includemap

usingnamespacestd;

typedeflonglongll;

constllmod=1000000007;

constdoubleep=-0x7ffffff;

structtrie

{

intcount;//统计当前前缀的个数

trie*next[26];//26个指针指下一个字母对应的节点

trie()//自己写个构造函数，就像是class，每次new的时候进行函数内的操作

{

count=1;

for(inti=0;i26;i++)next[i]=NULL;

}

};

voidbuild(trie*root,char*word)

{

trie*now=root;

inti=0;

while(word[i])

{

inttmp=word[i]-a;

if(now-next[tmp]NULL)//还没有这样的前缀就新加

{

trie*nextnewtrie();//每次都new新的节点，就不用在意数组开小了

now-next[tmp]=next;

}

else

{

now-next[tmp]-count++;//原先有这样的前缀就数量加一

}

now=now-next[tmp];//dfs往下找

i++;

}

}

intsearch(trie*root,char*word)

{

trie*now=root;

inti=0;

while(word[i])

{

inttmp=word[i]-a;

if(now-next[tmp]NULL)return0;//如果没有下一个那么就没有要找的前缀

now=now-next[tmp];

i++;

}

returnnow-count;//所有前缀字母都找完，而且没有return0过就输出前缀的数量

}

intmain()

{

intn,m;

inti,j;

charstr[50];

while(~scanf(%d%d,n,m))

{

trie*root=newtrie();//建一个跟节点，从这个跟开始建字典树