Longest Palindromic Sub-string

#include <cstdlib>
#include <iostream>
#include <ctime>

using namespace std;

/* 0~9, a~z, A~z */
void randstring(int n, char* s) {
  int fn = rand() % n;
  if (fn <= n/2)
    fn = (n+1) / 2;
  for (int i = 0; i < fn; i++) {
    int t = rand() % 3;
    char c;
    if (t == 0)
      s[i] = '0' + (rand()%10);
    else if (t == 1)
      s[i] = 'a' + (rand()%26);
    else
      s[i] = 'A' + (rand()%26);
  }
  for (int i = fn; i < n; i++) {
    s[i] = s[rand()%fn];
  }
}

int main() {
  srand(time(0));
  int n = 20;
  char* s = new char[n+1];
  s[n] = '\0';
  randstring(n, s);
  cout << s << endl;
  int n2 = (n+1)*2 + 1;
  char* ns = new char[n2];
  ns[0] = '$';
  ns[1] = '#';
  int j;
  int i;
  for (i = 0, j = 2; i < n; i++) {
    ns[j] = s[i];
    ns[++j] = '#';
    j++;
  }
  ns[j] = '#';
  ns[n2-1] = '\0';
  cout << ns << endl;
  int* p = new int[n2];
  for (i = 0; i < n2; i++)
    p[i] = 0;
  int mx = 0;
  int id = 0;
  int pid = 0;
  int pi = 0;
  for (i = 1; i < n2; i++) {
    p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
    while (ns[i + p[i]] == ns[i-p[i]]) p[i]++;
    if ((i + p[i]) > mx) {
      mx = i + p[i];
      id = i;
    }
    if (p[i] > pid) {
      pid = p[i];
      pi = i;
    }
  }
  cout << " ";
  for (i = 1; i < n2-1; i++)
    cout << p[i];
  cout << endl;
  cout << pid << " " << pi << endl;
  if (pid > 2) {
    for (i = pi - p[pi] + 1; i < pi + p[pi]; i++)
      if (ns[i] != '#')
        cout << ns[i];
  }
  cout << endl;
  delete []s;
  delete []ns;
  delete []p;
  return 0;
}

Find the minimum larger node in binary search tree for a giving node.

Question:
Find the minimum larger node in binary search tree for a giving node.
Answer:
struct BSTreeNode {
BSTreeNode* pLeft;
BSTreeNode* pRight;
BSTreeNode* pParent;
int value;
};
BSTreeNode* findMinLarge(BSTreeNode* node) {
if (!node)
return 0;
if (Node* result = node->pRight) {
while (result && result->pLeft) {
result = result->pLeft;
}
return result;
}
if (node->pParent == 0) {
return 0;
}
if (node->pParent->pLeft == node)
return node->pParent;
BSTreeNode* parent = node->pParent;
BSTreeNode* pparent = parent->pParent;
while (1) {
if (pparent && pparent->pLeft == parent) {
return pparent;
}
if (!pparent)
break;
parent = pparent;
pparent = parent->pParent;
}
return 0;
}

the devils out of the man

鬼被赶出

        耶稣问他说：“你名叫什么？”他说：“我名叫‘群’”；这是因为附着他的鬼多。 鬼就央求耶稣，不要吩咐他们到无底坑里去。那里有一大群猪在山上吃食。鬼央求耶稣，准他们进入猪里去。耶稣准了他们， 鬼就从那人出来，进入猪里去。于是那群猪闯下山崖，投在湖里淹死了。 (路加福音 8:30-33 和合本)

        And Jesus asked him, saying, What is thy name?And he said, Legion: because many devils were entered into him.And they besought him that he would not command them to go out into the deep.And there was there an herd of many swine feeding on the mountain: and they besought him that he would suffer them to enter into them. And he suffered them.Then went the devils out of the man, and entered into the swine: and the herd ran violently down a steep place into the lake, and were choked. (Luke 8:30-33 KJV)

         耶稣问这人的名字，得到的回答是群，这似乎是在说有一整个军团的鬼进到他里面（一个罗马军团约有六千个士兵）。可见这个人里面住了很多鬼。那些鬼知道它们必须离开这人，就不断恳求耶稣不要吩咐它们到无底坑里去。无底坑是拘禁群鬼、甚至撒但的所在（启二十1及下）。它们央求耶稣准许它们进到正在附近吃食的一大群猪里面去，耶稣准了它们，鬼就离了那人，进入猪里去。那猪群闯下山崖，投在湖里淹死了。这里可能有人会问耶稣竟牺牲猪群的主人来医治这个人？对这个问题，基本的答复应该是：这人的痊愈要比一群猪重要得多。可有任何人当真以为猪应该得救，而这人应该继续留在不得救的情景中吗？同样地，发拉尔指出：“对于全城而言，将邻舍从这野蛮疯子的危险和恐惧中释放出来，这个收益要比损失这群猪更大。”我们也要记得：耶稣既未打发鬼进到猪里去（祂不过是准许它们罢了），也没有打发猪投到湖里去（这故事并未说祂愿意猪死亡）。

Where is your faith?

这到底是谁？

耶稣对他们说：“你们的信心在哪里呢？”他们又惧怕又希奇，彼此说：“这到底是谁？他吩咐风和水，连风和水也听从他了。” (路加福音 8:25 和合本)

And he said unto them, Where is your faith?And they being afraid wondered, saying one to another, What manner of man is this! for he commandeth even the winds and water, and they obey him. (Luke 8:25 KJV)

祂查问，你们的信心在哪里呢？暗示门徒不该惧怕，他们应该信靠祂。可见耶稣希望门徒对祂有信心。他们对这件事的反应，仿佛是见了神的面一样。他们充满了敬畏（惧怕），他们惊奇地问：“这到底是谁？”这是重要的问题，路加不容他的读者忽略它。这件事情，更新了门徒对耶稣的认识，他们更深地认识了祂的奥秘和奇妙。这才是最大的收获。今日的世界，充满艰难试探，很多时候神的计划看起来似乎岌岌可危。基督似乎睡着了。但是，不要叫醒祂。不要以为神想藉着你我的手来保护方舟，来托起小船。祂不需要这样作。

Rebuild Binary Tree from Preorder and Inorder Traversal

Question:
struct NODE {
NODE* pLeft;
NODE* pRight;
char chValue;
};
e.g.
preorder traversal : a b d c e f
inorder traversal : d b a e c f

Answer:

include

using namespace std;

struct NODE {
NODE* pLeft;
NODE* pRight;
char chValue;
};

void PrintPreOrder(NODE* pRoot) {
if (!pRoot)
return;
cout << pRoot->chValue;
PrintPreOrder(pRoot->pLeft);
PrintPreOrder(pRoot->pRight);
}

void PrintInOrder(NODE* pRoot) {
if (!pRoot)
return;
PrintInOrder(pRoot->pLeft);
cout << pRoot->chValue;
PrintInOrder(pRoot->pRight);
}

void Rebuild(char* pPreOrder, char* pInOrder, int nTreeLen, NODE** pRoot) {
if (pPreOrder == 0 || pInOrder == 0)
return;
NODE* pTemp = new NODE;
pTemp->pLeft = 0;
pTemp->pRight = 0;
pTemp->chValue = *pPreOrder;
if (pRoot == 0)
pRoot = pTemp;
if (nTreeLen == 1)
return;
char pOrgInOrder = pInOrder;
char pLeftEnd = pInOrder;
int nTempLen = 0;
while (*pPreOrder != *pLeftEnd) {
nTempLen++;
if (nTempLen > nTreeLen)
break;
pLeftEnd++;
}
int nLeftLen = (int)(pLeftEnd - pOrgInOrder);
int nRightLen = nTreeLen - nLeftLen - 1;
if (nLeftLen > 0)
Rebuild(pPreOrder+1, pInOrder, nLeftLen, &(pTemp->pLeft));
if (nRightLen > 0)
Rebuild(pPreOrder+nLeftLen+1, pInOrder + nLeftLen + 1, nRightLen, &(pTemp->pRight));
}

int main() {
char* pPreOrder = "abdcef";
char* pInOrder = "dbaecf";
NODE* pRoot = 0;
int nTreeLen = 6;
Rebuild(pPreOrder, pInOrder, nTreeLen, &pRoot);
PrintPreOrder(pRoot);
cout << endl;
PrintInOrder(pRoot);
cout << endl;
return 0;
}

Array Right Shift K Steps

Question:
An array has N numbers, move each elements to right for K steps.
time limit : O(N)
e.g.
abcd1234 move 4 steps turns out
1234abcd
Answer:
void Reverse(int* arr, int b, int e)
{
for (; b < e; b++, e--) {
int temp = arr[e];
arr[e] = arr[b];
arr[b] = temp;
}
}
void RightShift(int* arr, int N, int K)
{
K %= N;
Reverse(arr, 0, N - K - 1);
Reverse(arr, N-K, N-1);
Reverse(arr, 0, N-1);
}

Therefore do not worry about tomorrow

“所以我告诉你们，不要为生命忧虑吃什么，喝什么；为身体忧虑穿什么。生命不胜于饮食吗？身体不胜于衣裳吗？  (马太福音 6:25 和合本)
“Therefore I tell you, do not worry about your life, what you will eat or drink; or about your body, what you will wear. Is not life more than food, and the body more than clothes? (Matthew 6:25 NIV)
你们看那天上的飞鸟，也不种，也不收，也不积蓄在仓里，你们的天父尚且养活它。你们不比飞鸟贵重得多吗？  (马太福音 6:26 和合本)
Look at the birds of the air; they do not sow or reap or store away in barns, and yet your heavenly Father feeds them. Are you not much more valuable than they? (Matthew 6:26 NIV)
你们哪一个能用思虑使寿数多加一刻呢（或译：使身量多加一肘呢） ？  (马太福音 6:27 和合本)
Can any one of you by worrying add a single hour to your life ? (Matthew 6:27 NIV)
何必为衣裳忧虑呢？你想野地里的百合花怎么长起来；它也不劳苦，也不纺线。  (马太福音 6:28 和合本)
“And why do you worry about clothes? See how the flowers of the field grow. They do not labor or spin. (Matthew 6:28 NIV)
然而我告诉你们，就是所罗门极荣华的时候，他所穿戴的，还不如这花一朵呢！  (马太福音 6:29 和合本)
Yet I tell you that not even Solomon in all his splendor was dressed like one of these. (Matthew 6:29 NIV)
你们这小信的人哪！野地里的草今天还在，明天就丢在炉里，　神还给它这样的妆饰，何况你们呢！  (马太福音 6:30 和合本)
If that is how God clothes the grass of the field, which is here today and tomorrow is thrown into the fire, will he not much more clothe you—you of little faith? (Matthew 6:30 NIV)
所以，不要忧虑说，吃什么？喝什么？穿什么？  (马太福音 6:31 和合本)
So do not worry, saying, ‘What shall we eat?’ or ‘What shall we drink?’ or ‘What shall we wear?’ (Matthew 6:31 NIV)
这都是外邦人所求的。你们需用的这一切东西，你们的天父是知道的。  (马太福音 6:32 和合本)
For the pagans run after all these things, and your heavenly Father knows that you need them. (Matthew 6:32 NIV)
你们要先求他的国和他的义，这些东西都要加给你们了。  (马太福音 6:33 和合本)
But seek first his kingdom and his righteousness, and all these things will be given to you as well. (Matthew 6:33 NIV)
所以，不要为明天忧虑，因为明天自有明天的忧虑；一天的难处一天当就够了。” (马太福音 6:34 和合本)
Therefore do not worry about tomorrow, for tomorrow will worry about itself. Each day has enough trouble of its own. (Matthew 6:34 NIV)