Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

后缀树47ms!!!我晕

Posted by KatrineYang at 2016-07-24 11:04:27 on Problem 3080
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator