POJ 2001 Shortest Prefixes（字典树入门）

本文主要是介绍POJ 2001 Shortest Prefixes（字典树入门），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

http://poj.org/problem?id=2001

题意：

找到多个字符串中，各自唯一的最短子串，例如 carte 与 carce 各自唯一的最短子串为cart与carc，即不会与其它字符串的子串重复。

思路:

字典树

解题心得:

更新关键值的时机很重要

代码：

#include<stdio.h>
#include<string>
typedef struct Node
{char c;int count;struct Node* next[26]; 
}Node;
Node* CreateNode()
{Node* T=(Node*)malloc(sizeof(Node));int i;for(i=0;i<26;i++){T->next[i]=NULL;}T->count=0;return T;
}
void insert(Node* T,char* str,int x)
{int len=strlen(str);//1.判断树根下是否存在st[i]int i;for(i=0;T->next[i]!=NULL;i++){//存在，更新count，并继续往下搜索。if(T->next[i]->c==str[x]){T->next[i]->count++;x++;//字符串结束if(x==len){return;}else{insert(T->next[i],str,x);return;}}}//2.不存在则建立节点if(T->next[i]==NULL){Node* temp=CreateNode();temp->c=str[x];temp->count=1;T->next[i]=temp;x++;if(x==len) return;else{insert(T->next[i],str,x);return;}}
}
void print(Node* T,char* str,int x)
{//寻找T下，关键值为str[x]的节点int i;int len=strlen(str);for(i=0;T->next[i]!=NULL;i++){if(T->next[i]->c==str[x]){if(T->next[i]->count==1){printf("%c",T->next[i]->c);return;}else{printf("%c",T->next[i]->c);x++;if(x<len) {print(T->next[i],str,x);}return;}}}
}
int main()
{char str[1001][30];Node* Tree=CreateNode();int i=0;while(gets(str[i])){Tree->count++;insert(Tree,str[i],0);i++;}int j;for(j=0;j<i;j++){printf("%s ",str[j]);print(Tree,str[j],0);printf("\n");}return 0;
}

这篇关于POJ 2001 Shortest Prefixes（字典树入门）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---