Trie – hahaschool

UVa 11488 Hyper Prefix Sets

January 22, 20152015-01-22hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <map>
#include <list>
#include <stack>

using namespace std;

#define MAXN 500000

struct trieNode{
    int next[2];
    int count;
    int dep;
} trie[MAXN];
int boundary = 1;

int main(){
    int casecnt;
    cin >> casecnt;
    while (casecnt--) {
        int n;
        boundary = 1;
        memset(trie, 0, sizeof(trie));
        cin >> n;
        for (int i = 1; i <= n; i++) {
            string toProc;
            cin >> toProc;
            int cur = 0;
            for (int i = 0; i < toProc.size(); i++) {
                if (trie[cur].next[toProc[i]-'0'] == 0) {
                    //create node;
                    trie[cur].next[toProc[i]-'0'] = boundary++;
                }
                cur = trie[cur].next[toProc[i]-'0'];
                trie[cur].count++;
                trie[cur].dep = i + 1;
            }
        }
        int res = 0;
        for (int i = 1; i < boundary; i++) {
            res = max(trie[i].dep*trie[i].count,res);
        }
        cout << res << endl;
    }


    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <map>

#include <list>

#include <stack>

using namespace std;

#define MAXN 500000

struct trieNode{

int next[2];

int count;

int dep;

} trie[MAXN];

int boundary = 1;

int main(){

int casecnt;

cin >> casecnt;

while (casecnt--) {

int n;

boundary = 1;

memset(trie, 0, sizeof(trie));

cin >> n;

for (int i = 1; i <= n; i++) {

string toProc;

cin >> toProc;

int cur = 0;

for (int i = 0; i < toProc.size(); i++) {

if (trie[cur].next[toProc[i]-'0'] == 0) {

//create node;

trie[cur].next[toProc[i]-'0'] = boundary++;

}

cur = trie[cur].next[toProc[i]-'0'];

trie[cur].count++;

trie[cur].dep = i + 1;

}

int res = 0;

for (int i = 1; i < boundary; i++) {

res = max(trie[i].dep*trie[i].count,res);

}

cout << res << endl;

}

return 0;

}

Trie树，静态方式的话（用数组保存节点），可以比较简单的实现遍历，动态方式（new＋指针）还要写搜索。。。

POJ 2503 Babelfish

January 20, 20152015-01-20hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <map>
#include <stack>

using namespace std;

map<string,string> dict;

int main(){
    ios_base::sync_with_stdio(false);
    string toProc;
    while (getline(cin,toProc) && toProc.size()) {
        string eng,dia;
        int i = 0;
        for (; i < toProc.size(); i++) {
            if (toProc[i] == ' ') {
                i++;
                break;
            }
            eng += toProc[i];
        }
        for (; i < toProc.size(); i++) {
            dia += toProc[i];
        }
        dict[dia] = eng;
    }
    while (cin >> toProc) {
        string toOut = dict[toProc];
        if (toOut.size()) {
            cout << toOut << endl;
        }else{
            cout << "eh" << endl;
        }

    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <map>

#include <stack>

using namespace std;

map<string,string> dict;

int main(){

ios_base::sync_with_stdio(false);

string toProc;

while (getline(cin,toProc) && toProc.size()) {

string eng,dia;

int i = 0;

for (; i < toProc.size(); i++) {

if (toProc[i] == ' ') {

i++;

break;

}

eng += toProc[i];

}

for (; i < toProc.size(); i++) {

dia += toProc[i];

}

dict[dia] = eng;

}

while (cin >> toProc) {

string toOut = dict[toProc];

if (toOut.size()) {

cout << toOut << endl;

}else{

cout << "eh" << endl;

}

return 0;

}

这个是拿map水过去的版本，其实应该自己手写一个的。。。

HDU 1251 统计难题

January 16, 20152015-01-16hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>

using namespace std;

struct trieNode{
    trieNode* child[30];
    int count;
    bool exist;
    trieNode(){
        memset(child, NULL, sizeof(child));
        count = 0;
        exist = false;
    }
} trie,*currNode;


int main(){
    string str;
    bool status = true;
    while (getline(cin,str)) {
        if (str.size() == 0) {
            status = false;
            continue;
        }
        if (status) {
            currNode = &trie;
            for (int i = 0; i < str.size(); i++) {
                if((*currNode).child[str[i]-'a'] == NULL){
                    (*currNode).child[str[i]-'a'] = new trieNode;

                }else{
                    (*currNode).child[str[i]-'a']->count++;
                    if (i == str.size()-1) (*currNode).child[str[i]-'a']->exist = true;
                }
                currNode = (*currNode).child[str[i]-'a'];
            }
        }else{
            currNode = &trie;
            bool flag = false;
            for (int i = 0; i < str.size(); i++) {
                if((*currNode).child[str[i]-'a'] == NULL){
                    break;
                }else{
                    if (i == str.size()-1) {
                        cout << (*currNode).child[str[i]-'a']->count+1<< endl;
                        flag = true;
                    }
                }
                currNode = (*currNode).child[str[i]-'a'];
            }
            if (!flag) {
                cout << 0 << endl;
            }

        }

    }

}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

using namespace std;

struct trieNode{

trieNode* child[30];

int count;

bool exist;

trieNode(){

memset(child, NULL, sizeof(child));

count = 0;

exist = false;

}

} trie,*currNode;

int main(){

string str;

bool status = true;

while (getline(cin,str)) {

if (str.size() == 0) {

status = false;

continue;

}

if (status) {

currNode = &trie;

for (int i = 0; i < str.size(); i++) {

if((*currNode).child[str[i]-'a'] == NULL){

(*currNode).child[str[i]-'a'] = new trieNode;

}else{

(*currNode).child[str[i]-'a']->count++;

if (i == str.size()-1) (*currNode).child[str[i]-'a']->exist = true;

}

currNode = (*currNode).child[str[i]-'a'];

}

}else{

currNode = &trie;

bool flag = false;

for (int i = 0; i < str.size(); i++) {

if((*currNode).child[str[i]-'a'] == NULL){

break;

}else{

if (i == str.size()-1) {

cout << (*currNode).child[str[i]-'a']->count+1<< endl;

flag = true;

}

currNode = (*currNode).child[str[i]-'a'];

}

if (!flag) {

cout << 0 << endl;

}

涨姿势了，new开辟的内存空间中变量是没有被初始化的，要自己写一个初始化的constructor才可以，否则就是RERERE。。。

然后Trie的实现方法基本就是这样，指针写法还是比较好弄的，但是以后还要考虑垃圾回收的问题。