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

## 后缀树写的，本地跑了好多随机接近100000长的数据秒出，为啥交上去就超时？？？我记得后缀树是O(n)的啊

Posted by KatrineYang at 2016-07-16 15:00:32 on Problem 2774 and last updated at 2016-07-16 15:04:05
```#include <iostream>
#include <cstdlib>
#include <map>
#include <cstring>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace std;

const char AnyChar = '\$';

int ans = 0;
int thres;

class node{
public:
map<char, node*> children;
node* parent;
node* suffix;
int start;
int end;
int pathLength;
int nodeDepth;
int minLeaf;
int maxLeaf;
int getNodeDepth();
void getMinmax();
//int number;
int number;//only leaf node

node(){
parent = NULL;
number = -1;
nodeDepth = -1;
children.clear();
minLeaf = -1;
maxLeaf = -1;
}

vector<int> getLeafNumber();
size_t getSize();
};

vector<int> node::getLeafNumber(){
vector<int> res;
if(number != -1){
//vector<int> res;
res.push_back(number);
return res;
}
for(map<char, node*>::iterator it = children.begin(); it != children.end(); it++){
vector<int> child_res = it->second->getLeafNumber();
for(int i = 0; i < child_res.size(); i++) res.push_back(child_res[i]);
}
return res;
}

void node::getMinmax(){
if(minLeaf != -1) return;
if(number != -1){
minLeaf = number;
maxLeaf = number;
return;
}
minLeaf = 2147483647, maxLeaf = -1;
for(map<char, node*>::iterator it = children.begin(); it != children.end(); it++){
it->second->getMinmax();
if(it->second->maxLeaf > maxLeaf) maxLeaf = it->second->maxLeaf;
if(it->second->minLeaf < minLeaf) minLeaf = it->second->minLeaf;
}
}

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* 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;
scanResult sR;
//cout << i << endl;
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;
}
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;
}
continue;
}
//cout << i << endl;

if(sR.offset == 0){//a node
scanResult sR1 = slowScan(sR.lastNode, i+1+sR.lastNode->pathLength, length);
if(sR1.offset == 0){//headi+1 is a node
node* iplus1 = new node;
nodeNumber ++;
iplus1->number = i+1;
iplus1->pathLength = length - i - 1;
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;
}
}
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;
}
//cout << i << endl;
}
}

void getAns(node *n){
//cout << n->number << " " << n->pathLength << " " << n->minLeaf << " " << n->maxLeaf << thres << endl;
if(n->minLeaf >= thres || n->maxLeaf <= thres) return;
int thisAns = n->pathLength;
if(thisAns > ans) ans = thisAns;
for(map<char, node*>::iterator it = n->children.begin(); it != n->children.end(); it++){
getAns(it->second);
}
}

void debug(node *n){
cout << n->number << " " << n->pathLength << " " << n->minLeaf << " " << n->maxLeaf << endl;
for(map<char, node*>::iterator it = n->children.begin(); it != n->children.end(); it++){
debug(it->second);
}
}

char c[200010] = {'\0'};

int main(int argc, char **argv){

int cnt;
scanf("%s",c);
thres = strlen(c);
c[thres] = '#';
scanf("%s", c+thres+1);
cnt = strlen(c);
c[cnt] = '\$';
cnt ++;
suffixTree st(c, cnt);

st.buildSuffixTree();

st.root->getMinmax();

getAns(st.root);
//debug(st.root);
cout << ans << endl;
return 0;
}
```

Followed by: