#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* 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){
	//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;
}

• ORZ会后缀树的dalao (2) RiseFalcon 2017-02-28 21:36:18