純粹就是為了寫模板而寫這個題...完全沒算法直接trie搞掉
Trie的動態思想我想也不用說了...顯然大家都知道...雖然指針確實很煩...調試了快半個小時才調試完畢
[cpp]
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
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 <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
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;
}
