学步园

无聊弄个字典树的模板。自己一直不是很懂字典树。。可能要学数据结构之后自己再深究一下。。这个比较重要。。

前缀：

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
#define MAXS 26
#define MAXL 22
#define MAXN 1005
char str[MAXN][MAXL];
struct node
{
 int num;//num表示用到该节点的字符串的个数,num=1时说明该节点是该字符串唯一的节点
 node *next[MAXS];
 node()
 {
  num=0;
  for(int i=0;i<MAXS;i++)
  {
   next[i]=NULL;
  }
 }
}*root;
void insert(node *rt,char *str)
{
 int i,id,len;
 len=strlen(str);
 for(i=0;i<len;i++)
 {
  id=str[i]-'a';
  if(rt->next[id]==NULL)
   rt->next[id]=new node();
  rt=rt->next[id];
  rt->num++;
 }
}
void serch(node *rt,char *s)
{
 int i,id,len;
 len=strlen(s);
 for(i=0;i<len;i++)
 {
  id=s[i]-'a';
  if(rt->num==1) //结束查找,已经找到了最短前缀
   break;
  printf("%c",s[i]);
  rt=rt->next[id];
 }
 printf("\n");
}
int main()
{
 
 int total=0;
 int i;
 root=new node();
 while(scanf("%s",&str[total])!=EOF)
 {
  insert(root,str[total]);
  total++;
 }
 for(i=0;i<total;i++)
 {
  printf("%s ",str[i]);
  serch(root,str[i]);
 }
 
 return 0;
}

对应的来个后缀的：

#include <iostream>
using namespace std;
const int MAXM = 30,KIND = 26;
int m;
struct node
{
    char* s;
    int prefix;
    bool isword;
    node* next[KIND];
    node()
    {
        s = NULL;
        prefix = 0;
        isword = false;
        memset(next,0,sizeof(next));
    }
}*root;//根
void insert(node *root,char *s)//插入
{
    node *p = root;
    for (int i = 0;s[i];i++)
    {
        int x = s[i] - 'a';
        p->s = s+i;
        if (p->next[x] == NULL)
            p->next[x] = new node;
        p = p->next[x];
        p->prefix++;
    }
    p->isword = true;
}
bool del(node *root,char *s)//删除
{
    node *p = root;
    for (int i = 0;s[i];i++)
    {
        int x = s[i] - 'a';
        if (p->next[x] == NULL)
            return false;
        p = p->next[x];
    }
    if (p->isword)
        p->isword = false;
    else
        return false;
    return true;
}
bool search(node *root,char* s)//查找
{
    node* p = root;
    for (int i = 0;s[i];i++)
    {
        int x = s[i]-'a';
        if (p->next[x] == NULL)
            return false;
        p = p->next[x];
    }
    return p->isword;
}
int count(node *root,char *s)//统计后缀
{
    node *p = root;
    for (int i = 0;s[i];i++)
    {
        int x = s[i] - 'a';
        if (p->next[x] == NULL)
            return 0;
        p = p->next[x];
    }
    return p->prefix;
}
int main()
{
    m = 0;
    root = new node;
    char s[MAXM];
    while (gets(s))
    {
        if (strcmp(s,"")==0)
            break;
        insert(root,s);
    }
    while (gets(s))
        printf("%d\n",count(root,s));
 return 0;
}