| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
先建立后缀树,然后DFS遍历计算子串长度以及计算叶节点数量,如果用unordered_map会更快#include <cstdio>
#include <map>
using namespace std;
const int MAX = 20005;
const int INF = 1000005;
int inline min(int a, int b) {
return a <= b ? a : b;
}
int inline max(int a, int b) {
return a >= b ? a : b;
}
int N, K, ans;
int milk[MAX];
struct Node {
int begin;
int end;
int depth;
Node* parent;
map<int, Node*> children;
Node* suffixLink;
Node(int begin, int end, int depth, Node* parent) {
this->begin = begin;
this->end = end;
this->parent = parent;
this->depth = depth;
this->children.clear();
}
};
class SuffixTree {
public:
Node* buildSuffixTree(int* s) {
Node* root = new Node(0, 0, 0, NULL);
Node* node = root;
for (int i = 0, tail = 0; i < N; ++i, ++tail) {
Node* last = NULL;
while (tail >= 0) {
Node* ch = node->children.find(s[i - tail]) != node->children.end() ? node->children[s[i - tail]] : NULL;
while (ch != NULL && tail >= ch->end - ch->begin) {
tail -= ch->end - ch->begin;
node = ch;
ch = ch->children.find(s[i - tail]) != ch->children.end() ?ch->children[s[i - tail]]: NULL;
}
if (ch == NULL) {
node->children[s[i]] = new Node(i, N, node->depth + node->end - node->begin, node);
if (last != NULL) last->suffixLink = node;
last = NULL;
} else {
int t = s[ch->begin + tail];
if (t == s[i]) {
if (last != NULL) last->suffixLink = node;
break;
} else {
Node* splitNode = new Node(ch->begin, ch->begin + tail, node->depth + node->end - node->begin, node);
splitNode->children[s[i]] = new Node(i, N, ch->depth + tail, splitNode);
splitNode->children[t] = ch;
ch->begin += tail;
ch->depth += tail;
ch->parent = splitNode;
node->children[s[i - tail]] = splitNode;
if (last != NULL) last->suffixLink = splitNode;
last = splitNode;
}
}
if (node == root) --tail;
else node = node->suffixLink;
}
}
return root;
}
int dfs(Node* node, int len) {
if (node->children.empty()) return 1;
int cnt = 0;
len += node->end - node->begin;
for (map<int, Node*>::iterator it = node->children.begin(); it != node->children.end(); ++it) {
cnt += dfs(it->second, len);
delete it->second;
}
if (cnt >= K && len > ans) ans = len;
return cnt;
}
};
int main() {
while (scanf("%d%d", &N, &K) != EOF) {
for (int i = 0; i < N; ++i) scanf("%d", &milk[i]);
++N;
milk[N - 1] = INF;
ans = 0;
SuffixTree st = SuffixTree();
Node* root = st.buildSuffixTree(milk);
st.dfs(root, 0);
printf("%d\n", ans);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator