nyoj 685 查找字符串

本文主要是介绍nyoj 685 查找字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

  当初一开始没做出来。
后来，学习过一段时间之后，在返回来做这道题，忽然发现，map类容器可以做。
PS：需要注意的是：此题如果用c++的输入输出的话，会超时。
O（time）：gets（）<  scanf（） < cin。  

附上代码：

#include<stdio.h>
#include<map>
#include<string>
#include<string.h>
using namespace std;
map<string,int> mp;
char s[17];
int main()
{//freopen("a.txt","r",stdin);int t;scanf("%d",&t);while(t--){int n,m;mp.clear();scanf("%d%d",&n,&m);getchar();while(n--){gets(s);//puts(s);mp[s]++;}while(m--){gets(s);printf("%d\n",mp[s]);}}return 0;
}

百度了一下，发现还可以用字典树做。

现学了一下字典树。

结构体：

typedef struct node
{struct node *next[MAX]; /*子节点个数 */int cnt;
}Trie;

ps：

<span style="white-space: pre;">	</span>Trie *root; /*定义根节点*/

一定要建立根节点并初始化。
关键核心就三个模块：

1、建树：

void creattree()
{int l=strlen(s);node *p=root,*q;for(int i=0; i<l; i++)  //对于每一位进行处理{int id=s[i]-'+';  //找到对应的位置if(p->next[id]==NULL){q=new node;q->cnt=0;for(int j=0; j<mx; j++)q->next[j]=NULL;p->next[id]=q;}p->next[id]->cnt++;p=p->next[id];}p->cnt=-1;  //一段的结束标志。
}

2、查找：

int find()
{int l=strlen(s);node *p=root;for(int i=0; i<l; i++){int id=s[i]-'+';if(p->next[id]==NULL)return -1;          // 找不到相同串if(p->next[id]->cnt==-1){if(i==l-1)return p->cnt;   //找到了相同串elsereturn -1;   //找到了目标的子串}p=p->next[id];}return 0;   //目标为某一串子串
}

3、 大多的字典树不要需释放内存，但是如果内存不够用，该应原还树空间

<span style="color:#464646;">int deleteTrie(Trie *T)
{int i;if(T==NULL)return 0;for(i=0;i<MAX;i++){if(T->next[i]!=NULL)deleteTrie(T->next[i]);}free(T);return 0;
}</span>

第三部分还没用到，暂时还不清楚效果。

这篇关于nyoj 685 查找字符串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---