登录 | 注册 |
趣题之家程序贴吧——Prefix_Worse
 



Prefix_Worse

基本信息:
提交人:Providence         提交日期:4/30/2005 6:34:30 PM        点击数:1154

编辑 删除

程序简介:

慢就一个字。。。

 

程序内容:  

#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;

const int black = 1, white = 0; //for LCA
const int maxn = 25000, maxnode = 100000, maxstr = 5000;
const int maxq = 1500010;

int tn, n, ancestor[maxnode], father[maxnode], color[maxnode];
struct TrieNode {
char ch;
int word, dph;
vector <int> child;
} trie[maxnode];
char st[maxstr];
int pos[maxn];

struct inpdata {
int data, order;
};

vector <inpdata> query[maxn];
int q, ans[maxq];

int find(int i, char j) { //trie find child
for (int t = 0; t < trie[i].child.size(); t ++)
if (trie[trie[i].child[t]].ch == j) return trie[i].child[t];
return 0;
}

void trie_insert(int id, char str[]) { //trie insert string
int i = 0, j = 0, t, tmp = strlen(str);
bool inside = true;

// scan constructed tree
while (t = find(i, str[j]), t > 0 && j < tmp) {
i = t; j ++;
}

// build new tree
while (j < tmp) {
inside = false;
trie[i].child.push_back(tn);
trie[tn].dph = trie[i].dph + 1;
trie[tn].ch = str[j];
trie[tn].word = -1;
i = tn; tn ++; j ++;
}

if (inside) {
trie[i].word = id;
pos[id] = i;
else {
trie[tn - 1].word = id;
pos[id] = tn - 1;
}
}

void make_set(int u) {
// disjoint_set make set
father[u] = u;
}

int find_set(int u) {
// disjoint_set find set
if (father[u] == u) return u;
else return father[u] = find_set(father[u]);
}

void union_set(int u, int v) {
// disjoint_set union set
father[find_set(u)] = find_set(v);
}

void lca(int u) {
// LCA
int i;

make_set(u);
ancestor[u] = u;
for (i = 0; i < trie[u].child.size(); i ++) {
lca(trie[u].child[i]);
union_set(u, trie[u].child[i]);
ancestor[find_set(u)] = u;
}
color[u] = black;

if (trie[u].word >= 0)
for (i = 0; i < query[trie[u].word].size(); i ++)
if (color[pos[query[trie[u].word][i].data]] == black)
ans[query[trie[u].word][i].order] = trie[ancestor[find_set(pos[query[trie[u].word][i].data])]].dph;
}

void init() {
int i, x, y;
tn = 1;
trie[0].ch = '~';
trie[0].dph = 0;
trie[0].word = -1;
for (i = 0; i < n; i ++) {
scanf("%s", &st);
trie_insert(i, st);
}

inpdata tmp;

scanf("%d", &q);
for (i = 0; i < q; i ++) {
scanf("%d%d", &x, &y);
x --; y --;
if (x == y)
ans[i] = trie[pos[x]].dph;
else {
tmp.data = y; tmp.order = i;
query[x].push_back(tmp);
tmp.data = x; tmp.order = i;
query[y].push_back(tmp);
}
}
}

int main() {
freopen("prefix.in", "r", stdin);
freopen("prefix.out", "w", stdout);

while (scanf("%d", &n) == 1) {
init();
lca(0);
for (int i = 0; i < q; i ++)
printf("%d\n", ans[i]);
}
return 0;
}



Microsoft OLE DB Provider for ODBC Drivers error '80004005'

[Microsoft][ODBC Microsoft Access Driver] Cannot update. Database or object is read-only.

/bbs/pascal_view.asp, line 345