Solutoin of LightOJ 1224 - DNA Prefix

See the problem 1224 - DNA Prefix 

/* Bismillahir Rahmanir Rahim Solution using "Trie" */ #include<bits/stdc++.h> using namespace std; long long k, i=0, x, cur, last, ss, sss, ans, mx; string s; struct node{ int next[4]; long long cnt; }ar[2500109]; void new_trie(int cur){ ar[cur].next[0]=-1; ar[cur].next[1]=-1; ar[cur].next[2]=-1; ar[cur].next[3]=-1; ar[cur].cnt=1; } int insrt(){ ss=s.size(), cur=0; for(k=0; k<ss; k++){ if(s[k]=='A') x=0; else if(s[k]=='C')x=1; else if(s[k]=='G')x=2; else if(s[k]=='T')x=3; if(ar[cur].next[x]==-1){ ar[cur].next[x]=last; new_trie(last++); cur=ar[cur].next[x]; } else{ cur=ar[cur].next[x]; ar[cur].cnt++; mx=(k+1)*ar[cur].cnt; ans=max(mx, ans); } } sss=max(ss, sss); } int main(){ long long t, n, cs=1; cin>>t; while(t--){ ans=0, mx=0, last=1, sss=0; new_trie(0); cin>>n; while(n--){ cin>>s; i++; insrt(); } cout<<"Case "<<cs++<<": "<<max(ans, sss)<<endl; } return 0; }

Solution of LightOJ 1129 - Consistency Checker

View the problem 1129 - Consistency Checker

 

// Solution using "Trie"

#include<bits/stdc++.h>
using namespace std;
long long n, m, t, cs=1, i, j, last=1, xx, cur, k, x, fl;
string s;

struct trie{
    bool endmark;
    int next[11];
}r[100009];

void new_trie(int cur){
    for(int zz=0; zz<10; zz++) r[cur].next[zz]=-1;
    r[cur].endmark=false;
}

void insrt(){
    cur=0, k=s.size();
    for(int z=0; z<k; z++){
        x=(int)s[z]-48;
        if(r[cur].next[x]==-1){
            r[cur].next[x]=last;
            new_trie(last++);
            cur=r[cur].next[x];
        }
        else{
            cur=r[cur].next[x];
            if(r[cur].endmark==true)fl=1;
            if(z==k-1) fl=1;
        }
        if(fl==1)break;
    }
    r[cur].endmark=true;
}

int main(){
    cin>>t;
    while(t--){
        cin>>n;
        fl=0, last=1;
        new_trie(0);
        for(i=0; i<n; i++){
            cin>>s;
            insrt();
        }
        cout<<"Case "<<cs++<<": ";
        if(fl==1) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}
 

Solution of POJ 2001-Shortest Prefixes

See the problem  POJ 2001-Shortest Prefixes

    // Solution using "Trie"

    #include<iostream>
    #include<vector>
    #include<string>
    using namespace std;
    vector<string>vt;
    vector<string>::iterator it;

    long long i, k, sz, cur, last, x;
    string s;

    struct node{
        int next[26+1];
        int cnt;
    }ar[20109];

    void new_trie(int cur){
        for(int j=0; j<26; j++)ar[cur].next[j]=-1;
        ar[cur].cnt=1;
    }

    void insrt(){
        cur=0, sz=s.size();
        for(i=0; i<sz; i++){
            x=s[i]-'a';
            if(ar[cur].next[x]==-1){
                ar[cur].next[x]=last;
                new_trie(last++);
                cur=ar[cur].next[x];
            }
            else{
                cur=ar[cur].next[x];
                ar[cur].cnt++;
            }
        }
    }

    void fnd(){
        sz=s.size(), cur=0;
        for(i=0; i<sz; i++){
            x=s[i]-'a';
            cout<<s[i];
            cur=ar[cur].next[x];
            if(ar[cur].cnt==1) i=sz;
        }
    }

    int main()
    {
        new_trie(0);
        last=1;
        while(getline(cin, s)){
            if(s.size()==0) break;
            vt.push_back(s);
            insrt();
        }
        for(it=vt.begin(); it<vt.end(); it++){
            s=*it;
            cout<<s<<" ";
            fnd();
            cout<<endl;
        }
        return 0;
    }