Monthly Archives: September 2014

hihoCoder 1032-最长回文子串

hihoCoder 1032-最长回文子串 #1032 : 最长回文子串 时间限制:1000ms 单点时限:1000ms 内存限制:64MB 描述 小Hi和小Ho是一对好朋友,出生在信息化社会的他们对编程产生了莫大的兴趣,他们约定好互相帮助,在编程的学习道路上一同前进。 这一天,他们遇到了一连串的字符串,于是小Hi就向小Ho提出了那个经典的问题:“小Ho,你能不能分别在这些字符串中找到它们每一个的最长回文子串呢?” 小Ho奇怪的问道:“什么叫做最长回文子串呢?” 小Hi回答道:“一个字符串中连续的一段就是这个字符串的子串,而回文串指的是12421这种从前往后读和从后往前读一模一样的字符串,所以最长回文子串的意思就是这个字符串中最长的身为回文串的子串啦~” 小Ho道:“原来如此!那么我该怎么得到这些字符串呢?我又应该怎么告诉你我所计算出的最长回文子串呢? 小Hi笑着说道:“这个很容易啦,你只需要写一个程序,先从标准输入读取一个整数N(N<=30),代表我给你的字符串的个数,然后接下来的就是我要给你的那N个字符串(字符串长度<=10^6)啦。而你要告诉我你的答案的话,只要将你计算出的最长回文子串的长度按照我给你的顺序依次输出到标准输出就可以了!你看这就是一个例子。” 提示一 提示二 提示三 提示四 样例输入 3 abababa aaaabaa acacdas 样例输出 7 5 3


这个题目有很多解法,具体可以看这里,其中的中心扩展法很有意思,不过时间复杂度$$O(n^2)$$。后来发现Manacher算法时间复杂度只要$$O(n)$$,膜拜之,无奈研究了很久也没理解,很多中文博客写得不够全面详细,直到我看了这篇文章,明白了。主要思路如下: 1. 首先将字符串S预处理成T。在S的字符之间插入#字符,如下:
For example: S = “abaaba”, T = “#a#b#a#a#b#a#”.
这样之后,不管S长度是奇数还是偶数,得到的T都是奇数,这样就不需要分情况讨论了,也方便了后面的求解。 2. 我们将中间结果存储在数组P中:
T = # a # b # a # a # b # a # P = 0 1 0 3 0 1 6 1 0 3 0 1 0
P[i]表示以T[i]为中心,T中回文串的半径,比如T[3]=b,P[3]=3,表示以b为中心,T中回文串的半径为3,也就是#a#b#a#,半径就是#a#,而P[3]=3也正好是原始串S中以b为中心的回文串的总长度,即回文串aba的长度为3. 所以我们只需要求出数组P,然后求P中的最大值即为S中最长回文串的长度。 3. 为了求数组P,有两种情况需要讨论。假设我们已经求出一部分数组P的值了,如下图所示: C为目前P中最大值的位置,C为目前T中使得R推进到最右边的回文串的中心位置center(不一定是P的最大值的位置,最大值还需要在最后一步求解),它的半径是9,所以左边(Left)到达L,右边(Right)到达R,下标分别是2和20. 4. 第一种情况是,如果此时i=13,则P[13]等于多少呢? i的对称点i’下标为9,P[i’]=1,它的回文串没有超出以C为中心的回文串,根据对称性,则P[i]=P[i’]=1. 5. 第二种情况是,如果i=15,则P[15]等于多少呢? 由图可知,i的对称点i’=7,P[i’]=7,即以i’为中心的回文串已经超出了以C为中心的回文串,L左边的红色线条即为超出部分。那么此时不能说P[i]=P[i’]=7,因为如果这样的话,那么以C为中心的回文串也可以扩展到红色线条部分,这样P[C]就大于原来的P[C]了。但是可以肯定的是,i的半径至少是R-i=5,所以我们可以在此基础上依次增加i的半径,判断是否还是回文串。 6. 总结一下就是:
if P[ i’ ] ≤ R – i, then P[ i ] ← P[ i’ ] else P[ i ] ≥ P[ i’ ]. (Which we have to expand past the right edge (R) to find P[ i ].
更详细的解释和部分代码实现请看原博文,下面是我的针对hihoCoder #1032 : 最长回文子串提交的代码: [cpp] #include&lt;iostream&gt; #include&lt;string&gt; using namespace std; //字符串预处理,插空#,首尾分别^&amp; string pre_process(string s) { string rs; int s_len=s.size(); if(s_len==0) return "^&amp;"; rs="^"; for(int i=0;i&lt;s_len;i++) //rs+="#"+s[i];//const char* 和int/char不能相加,指针越界 rs+="#"+s.substr(i,1);//const char*和string可以相加 return rs+"#&amp;"; } int get_longest_pal_len(string s) { string T=pre_process(s); int n=T.size(); int *P=new int[T.size()]; P[0]=0; int C=0,R=0; for(int i=1;i&lt;n-1;i++) { int i_mirror=2*C-i;//i的对称位置 P[i]=(R&gt;i)?min(R-i,P[i_mirror]):0;//如果R&gt;i,说明i还在R里面,如果P[i_mirror]&lt;=R-i,则类似图中i=13;如果P[i_mirror]&gt;R-i,则P[i]至少是R-i的,然后从R-i递增测试 while(T[i+1+P[i]]==T[i-1-P[i]]) P[i]++; if(i+P[i]&gt;R)//更新最大的中心点和右边界 { C=i; R=i+P[i]; } } int max_len=0; for(int i=1;i&lt;n-1;i++) { if(P[i]&gt;max_len)//寻找最大P[i],P[i]既是T[i]的回文串半径(包含#),也是以S[i]为中心的最长回文串长度。 max_len=P[i]; } delete[] P; return max_len; } int main() { int n; string s; cin&gt;&gt;n; while(n–) { cin&gt;&gt;s; cout&lt;&lt;get_longest_pal_len(s)&lt;&lt;endl; } return 0; } [/cpp] 这段代码有一小部分需要注意一下,就是string pre_process(string s);字符串预处理函数中的rs+=”#”+s.substr(i,1);不要写成了rs+=”#”+s[i];,因为”#”会隐式转换成const char*类型,而s[i]是char/int类型,”#”+s[i]相当于指针增加一个int偏移量,会导致指针越界。所以要写成”#”+s.substr(i,1),因为string.substr返回的是string类型,const char*和string是可以相加(连接)的。看来我还是基础不牢啊~ ]]>

hihoCoder week10-1-后序遍历

hihoCoder week10-1-后序遍历 题目1 : 后序遍历 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 在参与过了美食节之后,小Hi和小Ho在别的地方又玩耍了一阵子,在这个过程中,小Ho得到了一个非常有意思的玩具——一棵由小球和木棍连接起来的二叉树! 小Ho对这棵二叉树爱不释手,于是给它的每一个节点都标记了一个标号——一个属于A..Z的大写字母,并且没有任意两个节点的标号是一样的。小Hi也瞅准了这个机会,重新巩固了一下小Ho关于二叉树遍历的基础知识~就这样,日子安稳的过了两天。 这天,小Ho正好在求解这棵二叉树的前序、中序和后序遍历的结果,但是却在求出前序遍历和中序遍历之后不小心把二叉树摔到了地上,小球和木棍等零件散落了一地! 小Ho损失了心爱的玩具,正要嚎啕大哭起来,所幸被小Hi发现了,劝说道:“别着急,这不是零件都还在么?拼起来不就是了?” “可是我忘记了二叉树长什么样子了!”小Ho沮丧道。 “这个简单,你不是刚刚求出了这棵二叉树的前序和中序遍历的结果么,利用这两个信息就可以还原出整棵二叉树来哦!” “这样么?!!”小Ho止住了泪水,问道:“那要怎么做呢?” 没错!小Ho在这一周遇到的问题便是:给出一棵二叉树的前序和中序遍历的结果,还原这棵二叉树并输出其后序遍历的结果。 提示:分而治之——化大为小,化小为无 输入 每个测试点(输入文件)有且仅有一组测试数据。 每组测试数据的第一行为一个由大写英文字母组成的字符串,表示该二叉树的前序遍历的结果。 每组测试数据的第二行为一个由大写英文字母组成的字符串,表示该二叉树的中序遍历的结果。 对于100%的数据,满足二叉树的节点数小于等于26。 输出 对于每组测试数据,输出一个由大写英文字母组成的字符串,表示还原出的二叉树的后序遍历的结果。 样例输入 AB BA 样例输出 BA


解法一(已更新简洁版解法二) 简单来说就是根据前序遍历和中序遍历的结果求得后序遍历。这个题目如果用手算的话还简单些,但是要用程序实现,还真让我无从下手。不过可以明确的思路是:依次取前序遍历中的一个元素,找它在中序遍历中的位置,然后把中序遍历分成左右两部分,再在左右两部分递归求解。 递归的思路虽然简单,具体代码实现时有很多细节需要注意,我参考了这篇博文里面的用前序遍历和中序遍历重建二叉树的代码。但是代码好像有一点小问题,指针横飞,我根据《数据结构》P161整理如下: [cpp] #include<iostream> #include<string> #include<cstdlib> using namespace std; typedef struct node_t { char data; struct node_t* lchild; struct node_t* rchild; }node;//树的定义 //根据先序遍历和中序遍历还原树结构 void rebuild_tree_from_pre_in_order(string &pre_order,string in_order,int tree_len,node*& root)//注意node*&要带上&,表示node*root的引用,看数据结构P162 { if(pre_order==""||in_order=="") return; node *tmp=(node*)malloc(sizeof(node)); tmp->data=pre_order[0]; tmp->lchild=NULL; tmp->rchild=NULL; if(root==NULL) root=tmp;//这里改变了root指针的指向,所以传进来的时候要node*& root使用引用! if(tree_len==1) { pre_order=pre_order.substr(1); //每次取前序遍历的元素之后都要将其删除,并且要将结果带出去 return; } int i=0,left_len=0,right_len=0; while(pre_order[0]!=in_order[i])//找到先序遍历中的根在中序遍历中的位置,将中序遍历一分为二 i++; left_len=i; right_len=in_order.size()-i-1; pre_order=pre_order.substr(1);//每次取先序遍历的元素之后都要将其删除,如果tree_len!=1,则要先计算了left_len和right_len之后再删除 if(left_len>0) rebuild_tree_from_pre_in_order(pre_order,in_order.substr(0,left_len),left_len,root->lchild);//递归左子树 if(right_len>0) rebuild_tree_from_pre_in_order(pre_order,in_order.substr(i+1,right_len),right_len,root->rchild);//递归右子树 } //后序遍历 void post_order_print(node* root) { if(root!=NULL) { post_order_print(root->lchild); post_order_print(root->rchild); cout<<root->data; } } int main() { string pre_order,in_order; cin>>pre_order>>in_order; node* root=NULL; rebuild_tree_from_pre_in_order(pre_order,in_order,pre_order.size(),root); post_order_print(root); return 0; } [/cpp] 首先利用递归的思想重建二叉树,然后后序遍历输出。需要注意的是我把二叉树节点统一定义为node,重建函数 [cpp] void rebuild_tree_from_pre_in_order(string &pre_order,string in_order,int tree_len,node*& root) [/cpp] 传入的参数需要写成node*& root,也就是node* root指针的引用,如果是C语言里可以用二级指针,因为在这个函数内部对指针node* root进行了修改(if(root==NULL) root=tmp;),也就是改变了上一个node里的 node_t* lchild和node_t* rchild的指向,这是改变了指针的指向(指针本身的内容),所以需要传入指针的引用,如果只是想改变指针指向的内容node->data,可以只用node*,总之一句话,想改变什么就传入什么的指针,想改变int就传入int*或者int&,想改变node*就传入node**或者node*&,这个在链表里也有类似的应用。 还有一个通俗易懂的例子: [cpp] #include<stdio.h> #include<stdlib.h> #include<string.h> void get_memory(char*& buffer,int n) { buffer=(char*)malloc(sizeof(char)*n); } int main() { char *str=NULL; get_memory(str,20); strcpy(str,"Hello World!"); printf("%s",str); return 0; } [/cpp] 如果void get_memory(char*& buffer,int n);的形参buffer不是传入指针的引用的话,函数里malloc分配的内存只是分配给了char*的副本,并不会传出去,这样会导致内存泄露。 解法二(2015.4.16更新) 今天回头来看解法一真是笨拙,解法一先恢复了树的结构,然后求树的后序遍历。其实可以不用这么复杂,题目的提示已经很明确了,不知道当时为什么没有注意到。 具体解法是这样的,假设s,t分别为前序遍历和中序遍历,则s=根+左+右;t=左+根+右;根据s可以知道根节点,在t中查找根节点,可以把t分成左和右,因为s和t的左右孩子长度是一样的,所以也可以把s分成左和右。这样我们就分别有了左孩子和右孩子的前序和中序遍历,又可以递归上述过程。 通过这种方法,我们可以由前序和中序遍历直接得到后序遍历。具体代码如下: [cpp] #include<iostream> #include<string> using namespace std; //s前序,t中序 string get_post_order(string s,string t) { if(s=="") return ""; if(s.size()==1) return s; int i; for(i=0;i<t.size();i++) if(t[i]==s[0]) break; string s_left=s.substr(1,i); string s_right=s.substr(i+1);//如果i+1==长度,则返回空串,当i+1>长度时才抛出异常。 string t_left=t.substr(0,i); string t_right=t.substr(i+1); return get_post_order(s_left,t_left)+get_post_order(s_right,t_right)+s[0]; } int main() { string s,t; while(cin>>s>>t) cout<<get_post_order(s,t)<<endl; return 0; } [/cpp] 由于题目已经过期,没办法提交到hiho,我简单测试了几个例子,得到了正确的结果。]]>

hihoCoder 1015-KMP算法

hihoCoder 1015-KMP算法 #1015 : KMP算法 时间限制:1000ms 单点时限:1000ms 内存限制:256MB 描述 小Hi和小Ho是一对好朋友,出生在信息化社会的他们对编程产生了莫大的兴趣,他们约定好互相帮助,在编程的学习道路上一同前进。 这一天,他们遇到了一只河蟹,于是河蟹就向小Hi和小Ho提出了那个经典的问题:“小Hi和小Ho,你们能不能够判断一段文字(原串)里面是不是存在那么一些……特殊……的文字(模式串)?” 小Hi和小Ho仔细思考了一下,觉得只能想到很简单的做法,但是又觉得既然河蟹先生这么说了,就肯定不会这么容易的让他们回答了,于是他们只能说道:“抱歉,河蟹先生,我们只能想到时间复杂度为(文本长度 * 特殊文字总长度)的方法,即对于每个模式串分开判断,然后依次枚举起始位置并检查是否能够匹配,但是这不是您想要的方法是吧?” 河蟹点了点头,说道:”看来你们的水平还有待提高,这样吧,如果我说只有一个特殊文字,你能不能做到呢?“ 小Ho这时候还有点晕晕乎乎的,但是小Hi很快开口道:”我知道!这就是一个很经典的模式匹配问题!可以使用KMP算法进行求解!“ 河蟹满意的点了点头,对小Hi说道:”既然你知道就好办了,你去把小Ho教会,下周我有重要的任务交给你们!“ ”保证完成任务!”小Hi点头道。 提示一:KMP的思路 提示二:NEXT数组的使用 提示三:如何求解NEXT数组 输入 第一行一个整数N,表示测试数据组数。 接下来的N*2行,每两行表示一个测试数据。在每一个测试数据中,第一行为模式串,由不超过10^4个大写字母组成,第二行为原串,由不超过10^6个大写字母组成。 其中N<=20 输出 对于每一个测试数据,按照它们在输入中出现的顺序输出一行Ans,表示模式串在原串中出现的次数。 样例输入 5 HA HAHAHA WQN WQN ADA ADADADA BABABB BABABABABABABABABB DAD ADDAADAADDAAADAAD 样例输出 3 1 3 1


题目大意就是用KMP算法求解一个子串在主串中出现的次数。我们都知道常规KMP算法可以用来判断一个模式串t是否在主串s中出现过,以及出现的位置。但是这题要求我们求出出现的次数。我们只需要对KMP算法稍加修改即可。 KMP的详细介绍可以看这里,我是仔细看了学校发的李春葆版本《数据结构》P105,代码也基本上照搬课本,使用的是修正后的求nextval数组的KMP算法。具体代码如下: [cpp] #include<iostream> #include<string> using namespace std; int nextval[10001]; //改进的next数组求法 void get_nextval(const string &t) { int j=0,k=-1; nextval[0]=-1; int t_len=t.size(); while(j<t_len) { //t[k]表示前缀,t[j]表示后缀 if(k==-1||t[j]==t[k]) { j++; k++; //较之前next数组求法,改动在下面4行 if(t[j]!=t[k]) nextval[j]=k; //之前只有这一行 else nextval[j]=nextval[k]; // 继续递归 } else k=nextval[k]; // 递归往前找 } } //t为模式串,s为主串;返回t在s中出现的次数 int get_show_times_kmp(const string &t,const string &s) { int t_len=t.size(),s_len=s.size(),i=0,j=0; int times=0; //int *nextval=new int[t_len]; get_nextval(t); while(i<s_len) { if(j==-1||s[i]==t[j]) { i++; j++; } else j=nextval[j]; if(j==t_len) { times++; //i=i-t_len+1; //j=0;//如果匹配成功的话,无需从t的开头重新匹配,也是只要将t右滑j-k个位置。看《数据结构》P107 } } return times; } int main() { int n; string t,s;//t为模式串,s为主串 cin>>n; while(n–) { cin>>t>>s; cout<<get_show_times_kmp(t,s)<<endl; } return 0; } [/cpp] 我做的修改只有一处,就是KMP搜索的时候,如果j==t_len说明在主串s中找到了一个t的匹配,令times++,此时程序还不能结束,我们要让匹配继续下去,为了让while成立,修改while条件只有i<s_len。 其实这个思路是我后来看某大神的解法思考过后才想明白的。我最开始的想法是这样的:既然在t.j和s.i处匹配成功,要进行下一轮匹配时,就应该令j=0,i=i-t_len+1;,也就是从主串s匹配成功起始位置的下一个位置和模式串t的起始位置开始重新匹配。这样做虽然正确,但是TLE超时。后来我仔细看课本P107图4.10,假设$$t=t_0t_j$$ ,且$$t_j==s_i$$,因为$$t_0…t_{k-1}==t_{j-k}…t_{j-1}$$,所以如果要进行下一次匹配,也可以直接将$$t_0…t_{k-1}$$右滑到$$t_{j-k}…t_{j-1}$$的位置,也就是$$t_0…t_{k-1}==s_{i-k}…s_{i-1}$$,再依次判断$$s_i$$是否等于$$t_k$$。这其实就是令j=nextval[j]。所以当j==t_len的时候,不需要特别处理,直接下一次循环就好。这样可以节省很多时间。 以上代码在hiho中AC,用时226ms,内存7MB。]]>

hihoCoder 1000-A + B

hihoCoder 1000-A + B #1000 : A + B 时间限制:1000ms 单点时限:1000ms 内存限制:256MB 描述 求两个整数A+B的和 输入 输入包含多组数据。 每组数据包含两个整数A(1 ≤ A ≤ 100)和B(1 ≤ A ≤ 100)。 输出 对于每组数据输出A+B的和。 样例输入 1 2 3 4 样例输出 3 7


这是很多OJ上的第一题,纯测试用,代码如下: [cpp] #include<stdio.h> int main() { int a,b; while(scanf("%d%d",&a,&b)==2) printf("%d\n",a+b); return 0; } [/cpp] 第一题简单飘过。 ]]>

hihoCoder 1014-Trie树

hihoCoder 1014-Trie树 #1014 : Trie树 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 小Hi和小Ho是一对好朋友,出生在信息化社会的他们对编程产生了莫大的兴趣,他们约定好互相帮助,在编程的学习道路上一同前进。 这一天,他们遇到了一本词典,于是小Hi就向小Ho提出了那个经典的问题:“小Ho,你能不能对于每一个我给出的字符串,都在这个词典里面找到以这个字符串开头的所有单词呢?” 身经百战的小Ho答道:“怎么会不能呢!你每给我一个字符串,我就依次遍历词典里的所有单词,检查你给我的字符串是不是这个单词的前缀不就是了?” 小Hi笑道:“你啊,还是太年轻了!~假设这本词典里有10万个单词,我询问你一万次,你得要算到哪年哪月去?” 小Ho低头算了一算,看着那一堆堆的0,顿时感觉自己这辈子都要花在上面了… 小Hi看着小Ho的囧样,也是继续笑道:“让我来提高一下你的知识水平吧~你知道树这样一种数据结构么?” 小Ho想了想,说道:“知道~它是一种基础的数据结构,就像这里说的一样!” 小Hi满意的点了点头,说道:“那你知道我怎么样用一棵树来表示整个词典么?” 小Ho摇摇头表示自己不清楚。 提示一:Trie树的建立 “你看,我们现在得到了这样一棵树,那么你看,如果我给你一个字符串ap,你要怎么找到所有以ap开头的单词呢?”小Hi又开始考校小Ho。 “唔…一个个遍历所有的单词?”小Ho还是不忘自己最开始提出来的算法。 “笨!这棵树难道就白构建了!”小Hi教训完小Ho,继续道:“看好了!” 提示二:如何使用Trie树 提示三:在建立Trie树时同时进行统计! “那么现在!赶紧去用代码实现吧!”小Hi如是说道 输入 输入的第一行为一个正整数n,表示词典的大小,其后n行,每一行一个单词(不保证是英文单词,也有可能是火星文单词哦),单词由不超过10个的小写英文字母组成,可能存在相同的单词,此时应将其视作不同的单词。接下来的一行为一个正整数m,表示小Hi询问的次数,其后m行,每一行一个字符串,该字符串由不超过10个的小写英文字母组成,表示小Hi的一个询问。 在20%的数据中n, m<=10,词典的字母表大小<=2. 在60%的数据中n, m<=1000,词典的字母表大小<=5. 在100%的数据中n, m<=100000,词典的字母表大小<=26. 本题按通过的数据量排名哦~ 输出 对于小Hi的每一个询问,输出一个整数Ans,表示词典中以小Hi给出的字符串为前缀的单词的个数。 样例输入 5 babaab babbbaaaa abba aaaaabaa babaababb 5 babb baabaaa bab bb bbabbaab 样例输出 1 3


这一题题目提示得很清楚,使用Trie树,无奈本人才疏学浅,在看这个题之前不知道什么是Trie树,果断百度之,大意是Trie树是一棵字典树,根节点不存储字母,其余所有节点存储一个字母,所以它最多是一棵26叉树;从根节点到某个节点的一次遍历就是一个单词,这样的数据结构很适合用来字符串查找或者前缀匹配。 常规的Trie树定义如下: [cpp] #define MAX 26 typedef struct TrieNode //Trie结点声明 { bool isStr; //标记该结点处是否构成单词 struct TrieNode *next[MAX]; //儿子分支 }Trie; [/cpp] 关于常规Trie树的详细介绍请看此博文。 Trie树节点中的isStr是为了查找单词方便而定义的,但是本题只是为了给出以某字符串为前缀的单词的个数,也就是说我们查找的时候只是查找前缀,而不是查找一个完整的单词,所以可以不要isStr成员。 之前看《算法导论》第14章:数据结构的扩张,其中讲到一种顺序统计树的数据结构,该结构就是一棵红黑树,只是在每个节点中额外增加了一个size属性来记录以该节点为根节点的树子树的节点个数。利用这种数据结构可以在O(lgn)时间复杂度内找到第i小的关键字,真是太伟大了。 所以借着这一章的思路,我很快有了本题的解题思路。给Trie树的每个节点增加一个pre属性,用来表示所有以从根节点到该节点构成的字符串为前缀的单词的个数。 题目已经提示我们了
提示三:在建立Trie树时同时进行统计!
所以我们在建立Trie树的时候,通过改造博文中的insert函数,我们每插入一个单词,该单词遍历过的节点的pre值都加1。这样,当我们要查找以字符串s为前缀的单词个数时,只要查找到该字符串s的节点,节点的pre即为以s为前缀的单词的个数。具体的代码实现请看下面: [cpp] #include<iostream> #include<string> #include<cstdlib> using namespace std; const int MAX_C=26; typedef struct Tri_Node { int pre;//以“从根节点到该节点构成的字符串”为前缀的单词的个数 struct Tri_Node *next[MAX_C]; }Trie; //初始化一棵树 void init_Trie(Trie** t)//二级指针 { *t=(Trie*)malloc(sizeof(Trie)); (*t)->pre=0;//参数用了二级指针,这样才将修改的pre的值传出去 for(int i=0;i<MAX_C;i++) { (*t)->next[i]=NULL; } } //将字符串s插入到树中 void insert_node(Trie* root,const string s) { if(root==NULL||s=="") return; int s_size=s.size(); Trie *p=root; for(int i=0;i<s_size;i++) { if(p->next[s[i]-‘a’]==NULL) { Trie *tmp=NULL; init_Trie(&tmp); tmp->pre++; p->next[s[i]-‘a’]=tmp; p=p->next[s[i]-‘a’]; } else { p=p->next[s[i]-‘a’]; p->pre++; } } } //查找以s为前缀的单词的个数 int search_pre(Trie* root, const string s) { int s_size=s.size(); Trie* p=root; int i=0; int rs=0; for(i=0;i<s_size;i++) { if(p->next[s[i]-‘a’]!=NULL) { p=p->next[s[i]-‘a’]; rs=p->pre; } else break; } if(i==s_size) return rs; else return 0; } int main() { int n,m; cin>>n; string s; Trie* root=NULL; init_Trie(&root); while(n–) { cin>>s; insert_node(root,s); } cin>>m; while(m–) { cin>>s; cout<<search_pre(root,s)<<endl; } return 0; } [/cpp] 该代码提交的结果:AC,用时1728ms,内存67MB。 由于对C语言及其指针不熟,中间还出现过一些小错误,比如init_Trie(Trie** t);的参数需要使用二级指针才能将值传出去;malloc需要cstdlib头文件等。]]>