算法设计

#include <cstdlib>
#include <iostream>

using namespace std;
/*
class TTNode
{
 public:
      int lKey;
      int rKey;
      TTNode *left;
      TTNode *right;
      TTNode *center;
      TTNode()
       :lKey(0),
        rKey(0),
        left(NULL),
        center(NULL),
        right(NULL)
        {
        }
        ~TTNode() {}
        bool isLeaf() { return left = NULL; }
};      

class TTTree
{
public:
       static TTTree *Instance;
private:
     void SplitNode(TTNode * subroot, int &inval, TTNode *inptr, int &retval, TTNode * &retptr)
     {
          retptr = new TTNode();
          if (inval < subroot->lKey)
          {
               retval = subroot->lKey;
               subroot->lKey = inval;
               retptr->lKey = subroot->rKey;
               retptr->left = subroot->center;
               retptr->center = subroot->right;
               subroot->center = inptr;
          }
          else if (inval < subroot->rKey)
          {
               retval = inval;
               retptr->lKey = subroot->rKey;
               retptr->left = inptr;
               retptr->center = subroot->right;
          }
          else
          {
               retval = subroot->rKey;
               retptr->lKey = inval;
               retptr->left = subroot->right;
               retptr->center = inptr;
          }
          subroot->rKey = 0;
     }

 public:
     bool Find(TTNode *subroot, const int &k, int &result) const
     {
          if (subroot == NULL)
          {
               return false;
          }
          if (k == subroot->lKey)
          {
               result = subroot->lKey;
               return true;
          }
          if (subroot->rKey!= 0 && 
              subroot->rKey == k)
          {
               result = subroot->rKey;
               return true;
          }
          if (k < subroot->lKey)
          {
               return Find(subroot->left, k, result);
          }
          else if (subroot->rKey == 0 || 
                   subroot->rKey > k)
          {
               return Find(subroot->center, k, result);
          }
          else if (subroot->rKey < k)
          {
               return Find(subroot->right, k, result);
          }
     } 

     bool Insert(TTNode *subroot, int &e, int &retval, TTNode * &retptr)
     {
          int myretv;
          TTNode *myretp = NULL;
          if (subroot == NULL)
          {
               subroot = new TTNode();
               subroot->lKey = e;
          }
          else if (subroot->isLeaf())
          {
               if (subroot->rKey == 0)
               {
                    if (subroot->lKey < e)
                    {
                         subroot->rKey = e;
                    }               
                    else
                    {
                         subroot->rKey = subroot->lKey;
                         subroot->lKey = e;
                    }
               }
               else
               {
                    SplitNode(subroot, e, NULL, retval, retptr);  
               }
          }
          else if (subroot->lKey > e)
          {
               Insert(subroot->left, e, myretv, myretp);
          }
          else if (subroot->rKey == 0 ||
                   subroot->rKey > e)
          {
              Insert(subroot->center, e, myretv, myretp);
          }
          else 
          {
               Insert(subroot->right, e, myretv, myretp);
          }
               if (myretp != NULL)
               {
                    if (subroot->rKey != 0)
                    {
                         SplitNode(subroot, myretv, myretp, retval, retptr);
                    }
                    else 
                    {
                         if (myretv < subroot->lKey)
                         {
                              subroot->rKey = subroot->lKey;
                              subroot->lKey = myretv;
                              subroot->right = subroot->center;
                              subroot->center = myretp;
                         }
                         else
                         {
                              subroot->rKey =myretv;
                              subroot->right = myretp;
                         }
                    }
               }
          return true;
     }   
};
TTTree* TTTree::Instance = new TTTree();

class PAIR
{
 public:
     void *ptr;
     int key;
};
#define MAXREC 10
class BPNode
{
 public:
     PAIR recs[MAXREC];
     int numrec;
     BPNode *leftptr, *rightptr;
     bool isLeaf() const;
     bool isFull() const;
};*/

/*
void MergeArray(int a[], int b[], int len1, int len2, bool asc = true)
{
     int p1 = len1 - 1, p2 = 0;
     int offset2 = 1;
     if ((asc && a[0] > a[len1 - 1]) || 
          (!asc && a[0] < a[len1 - 1]))
     {
              int temp = 0;
              int end = len1 / 2;
              for (int i = 0; i < end; ++i) 
              {
                   temp = len1 - i - 1;
                   a[i] = a[i] + a[temp];
                   a[temp] = a[i] - a[temp];
                   a[i] = a[i] - a[temp];
              }
     }
     if ((asc && b[0] < b[len2 - 1]) ||
         (!asc && b[0] > b[len2 - 1]))
     {
          p2 = len2 - 1;
          offset2 = -1;
     }
     int p3 = len1 + len2;
     int prifix = asc ? 1 : -1;
         while((p1 >= 0) && (p2 >= 0 && p2 < len2))
         {
              int plusResult = (a[p1] - b[p2]) * prifix;
              if (plusResult > 0)
              {
                   a[--p3] = a[p1];
                   --p1;
              }
              else
              {
                   a[--p3] = b[p2];
                   p2 += offset2;
              }
         }
     while (p2 >= 0 && p2 < len2)
     {
         a[--p3] = b[p2];
         p2 += offset2;
     }
     for (int i = 0; i < len1 + len2; ++i)
     {
          cout << a[i] << " ";
     }
}
*/
void GetNext(char a[], int len, int next[])
{
     int i = 0, j = -1;
     next[0] = -1;
     while (i < len - 1)
     {
          if (j == -1 || a[i] == a[j])
          {
               ++j;
               ++i;
               if (i < len - 1)
               {
                   if (a[i] != a[j])
                   {
                        next[i] = j;
                   }
                   else
                   {
                        next[i]= next[j];
                   }
               }
          }
          else
          {
               j = next[j];
          }
     }
     for (i = 0; i < len - 1; ++i)
     {
          cout << next[i] << " ";
     } 
    cout << endl;
}

void GetNext1(char a[], int len, int next[])
{
     int i = 0, j = -1;
     next[0] = -1;
     while(i < len)
     {
          if (j == -1 || a[i] == a[j])
          {
               ++i;
               ++j;
               if (i < len - 1)
               {
                    next[i] = j;
               }
          }
          else
          {
               j = next[j];
          }
     }
     for (i = 0; i < len - 1; ++i)
     {
          cout << next[i] << " ";
     } 
    cout << endl;
}

void Print(char a[], int len)
{
     for (int i = 0; i < len; ++i)
     {
          cout << a[i];
     }
     cout << endl;
}

int main(int argc, char *argv[])
{
    //int a[9] = {9, 18, 27, 46, 55, 0, 0, 0, 0};
    //int b[4] = {1, 12, 333, 444};
    char a4[11] = "aaaabbbcab";
    Print(a4, 11);
    int next4[10] = {0};
    GetNext(a4, 11, next4);
    GetNext1(a4, 11, next4);

    char a3[11] = "aaaaaaaaab";
    Print(a3, 11);
    int next3[10] = {0};
    GetNext(a3, 11, next3);
    GetNext1(a3, 11, next3);


    char a2[11] = "ababcbbabb";
    Print(a2, 11);
    int next2[10] = {0};
    GetNext(a2, 11, next2);
    GetNext1(a2, 11, next2);


    char a1[7] = "aaaadd";
    Print(a1, 7);
    int next1[6] = {0};
    GetNext(a1, 7, next1);
    GetNext1(a1, 7, next1);
    

    char a5[9] = "abdabcde";
    Print(a5, 9);
    int next5[8] = {0};
    GetNext(a5, 9, next5);
    GetNext1(a5, 9, next5);

    system("PAUSE");
    return EXIT_SUCCESS;
}