#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

int findNumberFirst(const char *str, const char *dest, vector<int>& pvec)
{
 if (str == NULL || dest == NULL)
 return 0;

 int pos = 0;
 int lenStr = strlen(str);
 int lenDest = strlen(dest);

 if (lenStr < lenDest)
 return 0;

 int count = 0;
 while (pos <= lenStr - lenDest)
 {
 if (strncmp(str + pos, dest, strlen(dest)) == 0)
 {
  pvec.push_back(pos);
  pos += lenDest;
  count++;
 }
 else
 {
  pos++;
 }
 }

 return count;
}

int findNumberLast(const char *str, const char *dest, vector<int> &pvec)
{
 if (str == NULL || dest == NULL)
 return 0;

 int strLen = strlen(str);
 int destLen = strlen(dest);

 if (strLen < destLen)
 return 0;

 int pos = 0;
 while (pos <= strLen - destLen)
 {
 if (strncmp(str + pos, dest, strlen(dest)) == 0)
 {
  pos += destLen;
  pvec.push_back(pos - 1);
 }
 else
 {
  pos++;
 }
 
 }

 return pvec.size();
}

void replaceArray(char *str, const char *src, const char *dest)
{
 if (str == NULL || src == NULL || dest == NULL)
 return;

 vector<int> pvec;
 int strLen = strlen(str);
 int srcLen = strlen(src);
 int destLen = strlen(dest);

 if (strLen < srcLen)
 return;

 int posBefore = 0;
 int posAfter = 0;

 if (srcLen < destLen)
 {
 int count = findNumberLast(str, src, pvec);
 if (count <= 0)
  return;
 
 posAfter = strLen + count * (destLen - srcLen) - 1;
 posBefore = strLen - 1;

 while (count > 0 && posBefore >= 0)
 {
  if (pvec[count - 1] == posBefore)
  {
  posAfter -= destLen;
  strncpy(str + posAfter + 1, dest, strlen(dest));
  count--;
  posBefore--;
  }
  else
  {
  str[posAfter--] = str[posBefore--];
  }
 }
 }
 else if (strLen > destLen)
 {
 int count = findNumberFirst(str, src, pvec);
 if (count <= 0)
  return;

 posAfter = 0;
 posBefore = 0;

 int i = 0;
 while (count >= 0 && posBefore < strLen)
 {
  if (count > 0 && pvec[i] == posBefore)
  {
  strncpy(str + posAfter, dest, strlen(dest));
  posAfter += destLen;
  count--;
  posBefore += srcLen;
  i++;
  }
  else
  {
  str[posAfter++] = str[posBefore++];
  }
 }
 str[posAfter] = '\0';
 }
}

void main()
{ 
 char *str = new char[100];
 if (str == NULL)
 return;
 memset(str, '\0', 100);

 const char *src = " ";
 const char *dest = "%20";
//case1: 只有1個空格
 strcpy(str, " ");

 replaceArray(str, src, dest);
 cout << "str: " << str << endl;

 replaceArray(str, dest, src);
 cout << "str: " << str << endl;

//case2: 兩個空格
 strcpy(str, " ");

 replaceArray(str, src, dest);
 cout << "str: " << str << endl;

 replaceArray(str, dest, src);
 cout << "str: " << str << endl;

//case3: 正常情況
 strcpy(str, "we are happy");

 replaceArray(str, src, dest);
 cout << "str: " << str << endl;

 replaceArray(str, dest, src);
 cout << "str: " << str << endl;

//case3: 空格在前
 strcpy(str, " we are happy");

 replaceArray(str, src, dest);
 cout << "str: " << str << endl;

 replaceArray(str, dest, src);
 cout << "str: " << str << endl;

//case4: 空格在后
 strcpy(str, "we are happy ");

 replaceArray(str, src, dest);
 cout << "str: " << str << endl;

 replaceArray(str, dest, src);
 cout << "str: " << str << endl;

//case4: 沒空格
 strcpy(str, "wearehappy");

 replaceArray(str, src, dest);
 cout << "str: " << str << endl;

 replaceArray(str, dest, src);
 cout << "str: " << str << endl;

//case5: 兩邊一樣
 strcpy(str, "we are happy");

 replaceArray(str, src, dest);
 cout << "str: " << str << endl;

 src = "%20";
 assert(dest == "%20");
 replaceArray(str, dest, src);
 cout << "str: " << str << endl;
}