POJ 2001 Shortest Prefixes 动态Trie - c++编程基础

纯粹就是为了写模板而写这个题...完全没算法直接trie搞掉

Trie的动态思想我想也不用说了...显然大家都知道...虽然指针确实很烦...调试了快半个小时才调试完毕

[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
//typedef long long LL;
//typedef __int64 LL;
//typedef long double DB;
//typedef unisigned __int64 LL;
//typedef unsigned long long ULL;
#define EPS 1e-8
#define MAXN 1600
#define MAXE 300000
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define MOD 99991
//#define MOD 99990001
//#define MOD 1000000007
#define max(a,b) ((a)>(b) (a):(b))
#define min(a,b) ((a)<(b) (a):(b))
#define max3(a,b,c) (max(max(a,b),c))
#define min3(a,b,c) (min(min(a,b),c))
#define mabs(a) ((a<0) (-a):a)
//#define L(t) (t << 1) //Left son t*2
//#define R(t) (t << 1 | 1) //Right son t*2+1
//#define Mid(a,b) ((a+b)>>1) //Get Mid
//#define lowbit(a) (a&-a) //Get Lowbit
//int gcd(int a,int b){return b gcd(b,a%b):a;}
//int lcm(int a,int b){return a*b/gcd(a,b);}
//std::ios::sync_with_stdio(false);
struct alpha{
int len;
char a[21]; // string lenth <= 20;
}str[10005];
struct node{
int val;
node(){
val = 0;
}
node *next[26]; // next str
}root;
void Initial(node *t)
{
for(int i = 0;i < 26; i++)
t->next[i]=NULL;
}
void Insert(alpha s)
{
int length = s.len;
node *p = &root;
for(int i = 0; i < length; i++)
{
int tmp = s.a[i] - 'a';
if(p->next[tmp] == NULL)
{
p->next[tmp] = new node;
Initial(p->next[tmp]);
}
p = p->next[tmp];
p->val++;
}
}
void Find(alpha s)
{
int length = s.len;
node *p = &root;
for(int i = 0; i < length; i++)
{
int tmp = s.a[i] - 'a';
printf("%c",s.a[i]);
if(p->next[tmp] != NULL && p->next[tmp]->val == 1)
return ;
p = p->next[tmp];
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int cnt = 0;
Initial(&root);
while(scanf("%s",str[cnt].a) != EOF)
{
str[cnt].len = strlen(str[cnt].a);
Insert(str[cnt]);
cnt++;
}
for(int i = 0; i < cnt; i++)
{
printf("%s ",str[i].a);
Find(str[i]);
puts("");
}
return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
//typedef long long LL;
//typedef __int64 LL;
//typedef long double DB;
//typedef unisigned __int64 LL;
//typedef unsigned long long ULL;
#define EPS 1e-8
#define MAXN 1600
#define MAXE 300000
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define MOD 99991
//#define MOD 99990001
//#define MOD 1000000007
#define max(a,b) ((a)>(b) (a):(b))
#define min(a,b) ((a)<(b) (a):(b))
#define max3(a,b,c) (max(max(a,b),c))
#define min3(a,b,c) (min(min(a,b),c))
#define mabs(a) ((a<0) (-a):a)
//#define L(t) (t << 1) //Left son t*2
//#define R(t) (t << 1 | 1) //Right son t*2+1
//#define Mid(a,b) ((a+b)>>1) //Get Mid
//#define lowbit(a) (a&-a) //Get Lowbit
//int gcd(int a,int b){return b gcd(b,a%b):a;}
//int lcm(int a,int b){return a*b/gcd(a,b);}
//std::ios::sync_with_stdio(false);
struct alpha{
int len;
char a[21]; // string lenth <= 20;
}str[10005];
struct node{
int val;
node(){
val = 0;
}
n

POJ 2001 Shortest Prefixes 动态Trie (一)