[Tire树]poj 2001：Shortest Prefixes

大致题意：

    给出多个字符串，输出每个字符串的最短非公共前缀。

 

大致思路：

    tire的简单变形，每个节点加一个值来记录经过这个节点的字符串数即可。

 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include <algorithm>
using namespace std;
const int inf=1<<28;
const int nMax=500;
const int mMax=100005;
class nodea{
public:
    int id;
    int vis;  //前缀记录标志
    nodea *p[26];
    nodea(){
        vis=0;
        int i;
        id=-1;
        for(i=0;i<26;i++)p[i]=NULL;
    }
};

nodea *root;
int cnt;

int insert(char *s){
    int i;
    nodea *r=root;
    int l=strlen(s);
    for(i=0;i<l;i++){
        r->vis+=1;
        if(r->p[s[i]-'a']==NULL){
            r->p[s[i]-'a']=new nodea();
        }
        r=r->p[s[i]-'a'];
    }
    if(r->id==-1){
        r->id=cnt;
        r->vis+=1;
        cnt++;
    }
    return r->id;
}
void getnum(char *s){
    int i;
    nodea *r=root;
    int l=strlen(s);
    for(i=0;i<l;i++){
        r=r->p[s[i]-'a'];
        if(r->vis==1){
            for(int j=0;j<=i;j++){
                cout<<s[j];
            }
            cout<<endl;
            return;
        }
    }
    cout<<s<<endl;
}
char str[mMax][nMax];

int main(){
    int n,i,t=0;
    while(scanf("%s",str[0])!=EOF){
        t=1;      //字符串总数
        cnt=1;
        root=new nodea();
        insert(str[0]);
        while(scanf("%s",str[t])!=EOF){
            if(str[t][0]=='?')break;    //这句是在调试时加上的，无实际用处~~
            insert(str[t]);
            t++;
        }
        for(i=0;i<t;i++){
            cout<<str[i]<<" ";
            getnum(str[i]);
        }
    }
    return 0;
}