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