| ||||||||||
| 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 | |||||||||
后缀树47ms!!!我晕#include <iostream>
#include <cstdlib>
#include <map>
#include <cstring>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stdio.h>
using namespace std;
const char AnyChar = '$';
int depth = 0, arg = -1;
class node{
public:
map<char, node*> children;
node* parent;
node* suffix;
int start;
int end;
int pathLength;
int nodeDepth;
int leaves[10];
//bool quan;
//int minLeaf;
//int maxLeaf;
int getNodeDepth();
//void getMinmax();
void getLeaves(int);
//int number;
int number;//only leaf node
node(){
parent = NULL;
number = -1;
nodeDepth = -1;
children.clear();
//minLeaf = -1;
// maxLeaf = -1;
for(int i = 0; i < 10; i++){
leaves[i] = -1;
}
// quan = false;
}
// vector<int> getLeafNumber();
//size_t getSize();
};
void node::getLeaves(int N){
if(number != -1){
if(number%61 == 60) return;
leaves[number/61] = number;
}
for(map<char, node*>::iterator it = children.begin(); it != children.end(); it++){
it->second->getLeaves(N);
for(int i = 0; i < N; i++){
if(leaves[i] == -1 && it->second->leaves[i] != -1){
leaves[i] = it->second->leaves[i];
}
}
}
}
class scanResult{
public:
node* lastNode;
char direction;
int offset;
scanResult(node* n, char c, int o): direction(c), offset(o), lastNode(n){}
scanResult(){}
};
class suffixTree{
public:
node* root;
char *str;
int length;
//int nodeNumber;
suffixTree(char *s, int l){
root = new node;
// nodeNumber = 1;
length = l;
str = s;
root->parent = root;
root->start = 0;
root->end = 0;
root->suffix = root;
root->pathLength = 0;
root->nodeDepth = 0;
}
~suffixTree(){
delete root;
}
scanResult fastScan(node* startNode, int startOffset, int endOffset);
scanResult slowScan(node* startNode, int startOffset, int endOffset);
node* slowScan(node* startNode, string targetString, int startOffset, int endOffset);
void buildSuffixTree();
vector<int> search(string searchString);
size_t getSize();
};
scanResult suffixTree::fastScan(node* startNode, int startOffset, int endOffset){
int remain = endOffset - startOffset;
node* currentNode = startNode;
while(remain >= 0){
char pivotChar = str[endOffset - remain];
node* next = currentNode->children[pivotChar];
int thisSpan = next->end - next->start;
if(remain == 0){
return scanResult(currentNode, AnyChar, 0);
}
else if(thisSpan <= remain){
remain -= thisSpan;
currentNode = next;
continue;
}
else{
return scanResult(currentNode, pivotChar, remain);
}
}
}
scanResult suffixTree::slowScan(node* startNode, int startOffset, int endOffset){
//cout << 1 << endl;
int i = startOffset;
node* currentNode = startNode;
while(i < endOffset){
if(currentNode->children.find(str[i]) == currentNode->children.end()){
return scanResult(currentNode, AnyChar, 0);
}
node* next = currentNode->children[str[i]];
int thisLength = next->end - next->start;
int j = 0;
while(j < thisLength){
if(str[i + j] != str[next->start + j]){
return scanResult(currentNode, str[i], j);
}
j++;
}
i += thisLength;
currentNode = next;
}
}
node* suffixTree::slowScan(node* startNode, string targetString, int startOffset, int endOffset){
int i = startOffset;
node* currentNode = startNode;
while(i < endOffset){
if(currentNode->children.find(targetString[i]) == currentNode->children.end()){
return NULL;
}
node* next = currentNode->children[targetString[i]];
int thisLength = next->end - next->start;
int j = 0;
while(j < thisLength){
if(i + j == endOffset){
return next;
}
if(targetString[i + j] != str[next->start + j]){
return NULL;
}
j++;
}
i += thisLength;
currentNode = next;
}
return currentNode;
}
void suffixTree::buildSuffixTree(){
node* headi = root, *headiplus1 = NULL;
node* wholeString = new node;
//nodeNumber ++;
wholeString->parent = root;
wholeString->number = 0;
wholeString->start = 0;
wholeString->end = length;
wholeString->pathLength = length;
root->children.insert(make_pair(str[0], wholeString));
//wholeString->nodeDepth = 1;
//cout << length << endl;*/
for(int i = 0; i < length - 1; i++){
//cout << i << endl;
node* pheadi = headi->parent;
node* spheadi = pheadi->suffix;
node* sheadi;
scanResult sR;
int startOffset = headi->start, endOffset = headi->end;
if(headi == root){
//cout << i << endl;
//sheadi = root;
sR = slowScan(root, i+1, length);
//cout << i << endl;
if(sR.offset == 0){//at a node
node* currentNode = sR.lastNode;
node* newNode = new node;
//nodeNumber ++;
newNode->parent = currentNode;
newNode->number = i+1;
newNode->pathLength = length - i - 1;
//newNode->nodeDepth = currentNode->nodeDepth + 1;
newNode->start = currentNode->pathLength + i + 1;
newNode->end = length;
currentNode->children.insert(make_pair(str[newNode->start], newNode));
//cout << newNode->start << endl;
headiplus1 = currentNode;
}
else{
//cout << i << endl;
node* lastNode = sR.lastNode;
node* nextNode = lastNode->children[sR.direction];
node* middleNode = new node;
node* newNode = new node;
//nodeNumber += 2;
middleNode->parent = lastNode;
//middleNode->nodeDepth = lastNode->nodeDepth + 1;
lastNode->children[sR.direction] = middleNode;
nextNode->parent = middleNode;
//nextNode->nodeDepth = middleNode->nodeDepth + 1;
newNode->parent = middleNode;
//newNode->nodeDepth = middleNode->nodeDepth + 1;
newNode->number = i+1;
char newDNextNode = str[nextNode->start + sR.offset];
middleNode->children[newDNextNode] = nextNode;
newNode->pathLength = length - i - 1;
middleNode->pathLength = lastNode->pathLength + sR.offset;
char newDNewNode = str[i + 1 + middleNode->pathLength];
middleNode->children[newDNewNode] = newNode;
newNode->start = middleNode->pathLength + i + 1;
newNode->end = length;
int separate = nextNode->start + sR.offset;
middleNode->start = nextNode->start;
middleNode->end = separate;
nextNode->start = separate;
headiplus1 = middleNode;
}
headi = headiplus1;
continue;
}
//cout << i << endl;
if(pheadi == root) startOffset ++;
sR = fastScan(spheadi, startOffset, endOffset);
if(sR.offset == 0){//a node
headi->suffix = sR.lastNode;
scanResult sR1 = slowScan(sR.lastNode, i+1+sR.lastNode->pathLength, length);
if(sR1.offset == 0){//headi+1 is a node
headiplus1 = sR1.lastNode;
node* iplus1 = new node;
//nodeNumber ++;
iplus1->number = i+1;
iplus1->pathLength = length - i - 1;
iplus1->parent = headiplus1;
//iplus1->nodeDepth = headiplus1->nodeDepth + 1;
char direction = str[i+1+headiplus1->pathLength];
headiplus1->children[direction] = iplus1;
iplus1->start = i+1+headiplus1->pathLength;
iplus1->end = length;
}
else{
node* lastNode = sR1.lastNode;
node* nextNode = lastNode->children[sR1.direction];
node* middleNode = new node;
node* newNode = new node;
// nodeNumber += 2;
middleNode->parent = lastNode;
//middleNode->nodeDepth = lastNode->nodeDepth + 1;
lastNode->children[sR1.direction] = middleNode;
nextNode->parent = middleNode;
//nextNode->nodeDepth = middleNode->nodeDepth + 1;
newNode->parent = middleNode;
//newNode->nodeDepth = middleNode->nodeDepth + 1;
newNode->number = i+1;
char newDNextNode = str[nextNode->start + sR1.offset];
middleNode->children[newDNextNode] = nextNode;
newNode->pathLength = length - i - 1;
middleNode->pathLength = lastNode->pathLength + sR1.offset;
char newDNewNode = str[i + 1 + middleNode->pathLength];
middleNode->children[newDNewNode] = newNode;
newNode->start = middleNode->pathLength + i + 1;
newNode->end = length;
int separate = nextNode->start + sR1.offset;
middleNode->start = nextNode->start;
middleNode->end = separate;
nextNode->start = separate;
headiplus1 = middleNode;
}
}
else{
node* lastNode = sR.lastNode;
node* nextNode = lastNode->children[sR.direction];
node* middleNode = new node;
node* newNode = new node;
// nodeNumber += 2;
middleNode->parent = lastNode;
lastNode->children[sR.direction] = middleNode;
nextNode->parent = middleNode;
newNode->parent = middleNode;
newNode->number = i+1;
char newDNextNode = str[nextNode->start + sR.offset];
middleNode->children[newDNextNode] = nextNode;
newNode->pathLength = length - i - 1;
middleNode->pathLength = lastNode->pathLength + sR.offset;
char newDNewNode = str[i + 1 + middleNode->pathLength];
middleNode->children[newDNewNode] = newNode;
newNode->start = middleNode->pathLength + i + 1;
newNode->end = length;
int separate = nextNode->start + sR.offset;
middleNode->start = nextNode->start;
middleNode->end = separate;
nextNode->start = separate;
headiplus1 = middleNode;
headi->suffix = middleNode;
}
headi = headiplus1;
//cout << i << endl;
}
}
void getAns(node *n, int N){
bool keyi = true;
for(int i = 0; i < N; i++){
if(n->leaves[i] == -1){
keyi = false;
break;
}
}
if(!keyi) return;
if(depth < n->pathLength){
depth = n->pathLength;
arg = n->leaves[0];
}
for(map<char, node*>::iterator it = n->children.begin(); it != n->children.end(); it++){
getAns(it->second, N);
}
}
void debug(node *n){
cout << n->number << " " << n->pathLength << endl;
for(map<char, node*>::iterator it = n->children.begin(); it != n->children.end(); it++){
debug(it->second);
}
}
//char c[1000] = {'\0'};
char endChar[11] = "BDEFHIJKLM";
int main(int argc, char **argv){
int cases;
scanf("%d", &cases);
for(int ii = 0; ii < cases; ii++){
char c[1000] = {'\0'};
int N;
scanf("%d", &N);
for(int i = 0; i < N; i++){
char ctemp[66];
scanf("%s", ctemp);
for(int j = i*61; j < (i+1)*61-1; j++){
c[j] = ctemp[j-i*61];
}
c[(i+1)*61-1] = endChar[i];
}
c[61*N-1] = '$';
suffixTree st(c, 61*N);
st.buildSuffixTree();
st.root->getLeaves(N);
depth = 0;
arg = -1;
getAns(st.root, N);
if(depth < 3){
printf("no significant commonalities\n");
}
else{
for(int i = 0; i < depth; i++){
printf("%c", c[arg+i]);
}
printf("\n");
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator