趣题之家程序贴吧——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 |