Next Spaceship

Driving into future…

POJ 2001 Shortest Prefixes Report

| Comments

View the Problem.

This problem can be solved by 2 methods.

  • Trie
  • Quick Sort

To get a quick coding, choose the Quick Sort method. To get a good performance, choose the Trie method.

POJ 2001 Shortest Prefixes (Trie)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <string.h>
using namespace std;
#define N 26
#define B 'a'

struct Trie{
    int num;
    Trie* child[N];
};
Trie* NewTrie(){
    Trie* tmp=new Trie();
    tmp->num=1;
    int i;
    for(i=0;i<N;i++){
        tmp->child[i]=NULL;
    }
    return tmp;
}

void Insert(Trie* tr,char* c,int l){
    int i;
    Trie* tmp=tr;
    for(i=0;i<l;i++){
        if(tmp->child[c[i]-B]==NULL){
            tmp->child[c[i]-B]=NewTrie();
        }
        else{
            tmp->child[c[i]-B]->num++;
        }
        tmp=tmp->child[c[i]-B];
    }
}
void Delete(Trie* tr){
    int i;
    for(i=0;i<N;i++){
        if(tr->child[i]) Delete(tr->child[i]);
    }
    delete tr;
    tr=0;
}
void Find(Trie* tr,char* c,int l){
    int i;
    printf("%s ",c);
    Trie* tmp=tr;
    for(i=0;i<l;i++){
        printf("%c",c[i]);
        if(tmp->child[c[i]-B]->num==1)
            break;
        tmp=tmp->child[c[i]-B];
    }
    printf("\n");
}
Trie* t;
char s[1001][21];
int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    t=NewTrie();
    int i=0,j;
    while(scanf("%s",s[i])!=EOF){
        Insert(t,s[i],strlen(s[i]));
        i++;
    }
    for(j=0;j<i;j++){
        Find(t,s[j],strlen(s[j]));
    }
    Delete(t);
    return 0;
}
POJ 2001 Shortest Prefixes (Quick Sort)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <algorithm>
#include <memory.h>
#include <string.h>
#define M 1100
using namespace std;
char c[M][30];
int d[M],l[M];
int n;
bool cmp(int x,int y){
    int i=0;
    while(c[x][i]==c[y][i]&&c[x][i]&&c[y][i])
        i++;
    return c[x][i]<c[y][i];
}
int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    int i,j,k,j2;
    n=0;
    while(scanf("%s",c[n])!=EOF){
        d[n]=n;
        n++;
    }
    sort(d,d+n,cmp);
    memset(l,0,sizeof(l));
    for(i=0;i<n-1;i++){
        int j=d[i];j2=d[i+1];
        k=0;
        while(c[j][k]==c[j2][k]&&c[j][k]&&c[j2][k])
            k++;
        if(k>l[j])l[j]=k;
        if(k>l[j2])l[j2]=k;
    }
    for(i=0;i<n;i++){
        if(c[i][0]){
            printf("%s ",c[i]);
            for(j=0;j<l[i];j++)
                printf("%c",c[i][j]);
            if(c[i][j]!=0)
                printf("%c",c[i][j]);
        }
        printf("\n");
    }
    return 0;
}
/*

#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<assert.h>
using namespace std;
int k[1000],l[1000];
char str1[1000][22];
int cmp1(int a,int b)
{
    int i=0;
    while(str1[a][i]==str1[b][i]&&str1[a][i]){
        i++;
    }
    return str1[a][i]<str1[b][i];
}
int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    int i=0,m1=0,m2=0,j,len,min;
    while (cin>>str1[i])
    {
          k[i]=i;
          i++;
    }
    len=i;
    sort(k,k+len,cmp1);
    for (i=0;i<len-1;i++)
    {
        j=0;
        while(str1[k[i]][j]&&str1[k[i+1]][j]&&str1[k[i]][j]==str1[k[i+1]][j])
            j++;
        if(j>l[k[i]])l[k[i]]=j;
        if(j>l[k[i+1]])l[k[i+1]]=j;
    }
    for (i=0;i<len;i++){
        cout<<str1[i]<<" ";
        for(j=0;j<l[i];j++){
            printf("%c",str1[i][j]);
        }
        if(str1[i][l[i]])printf("%c",str1[i][l[i]]);
        cout<<endl;
    }
    return 0;  
}

*/

Comments