Problem
find a pattern in byte array and change that pattern in place (do not use temp array or variable)
for example, find pattern 0,0,3 in an byte array and replace it with 0,0 should be o(n)
Solution
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <iterator>
using namespace std;
void ReplacePattern(int* arr, int& len)
{
int index1 = 2;
int index2 = 2;
while(index2 < len){
if(!(arr[index1 -2 ] == 0 && arr[index1-1] == 0 && arr[index2] == 3)){
arr[index1++] = arr[index2];
}
index2 ++;
}
len = index1;
}
void InitArray(int* arr, int len)
{
for(int i = 0; i < len; ++i){
arr[i] = rand() % 4;
}
}
int main(int argc, char* argv[])
{
srand(3);
int arr[] = {1, 0, 0, 3, 3, 0, 0, 3, 1, 2, 3, 0, 0, 3, 0, 3, 1, 0, 0, 3};
int len = sizeof(arr)/ sizeof(arr[0]);
cout << "Before pattern replacing" << endl;
copy(arr, arr + len, ostream_iterator<int>(cout, " "));
cout << endl;
ReplacePattern(arr, len);
cout << "After pattern replacing" << endl;
copy(arr, arr + len, ostream_iterator<int>(cout, " "));
cout << endl;
for(int i = 10; i < 20; ++i){
int len = sizeof(arr)/ sizeof(arr[0]);
InitArray(arr, len);
cout << "Before pattern replacing" << endl;
copy(arr, arr + len, ostream_iterator<int>(cout, " "));
cout << endl;
ReplacePattern(arr, len);
cout << "After pattern replacing" << endl;
copy(arr, arr + len, ostream_iterator<int>(cout, " "));
cout << endl << "--------------------" << endl;
}
return 0;
}
Output
Before pattern replacing
1 0 0 3 3 0 0 3 1 2 3 0 0 3 0 3 1 0 0 3
After pattern replacing
1 0 0 0 0 1 2 3 0 0 0 1 0 0
Before pattern replacing
0 0 2 3 3 1 2 3 1 0 1 1 3 0 2 3 3 1 1 2
After pattern replacing
0 0 2 3 3 1 2 3 1 0 1 1 3 0 2 3 3 1 1 2
--------------------
Before pattern replacing
2 2 0 2 2 3 3 3 0 1 1 0 1 0 1 3 3 1 1 0
After pattern replacing
2 2 0 2 2 3 3 3 0 1 1 0 1 0 1 3 3 1 1 0
--------------------
Before pattern replacing
1 0 2 3 2 0 0 3 1 0 0 1 0 0 3 3 1 1 1 1
After pattern replacing
1 0 2 3 2 0 0 1 0 0 1 0 0 1 1 1 1
--------------------
Before pattern replacing
2 0 2 1 0 2 3 2 1 0 0 0 0 1 0 2 1 0 2 0
After pattern replacing
2 0 2 1 0 2 3 2 1 0 0 0 0 1 0 2 1 0 2 0
--------------------
Before pattern replacing
1 2 3 1 0 1 3 0 2 2 0 3 3 0 1 0 3 1 0 3
After pattern replacing
1 2 3 1 0 1 3 0 2 2 0 3 3 0 1 0 3 1 0 3
--------------------
Before pattern replacing
0 1 3 3 1 0 3 0 3 1 1 2 2 1 0 0 2 0 0 3
After pattern replacing
0 1 3 3 1 0 3 0 3 1 1 2 2 1 0 0 2 0 0
--------------------
Before pattern replacing
2 2 1 0 1 0 3 3 3 2 1 2 2 0 3 1 2 0 0 3
After pattern replacing
2 2 1 0 1 0 3 3 3 2 1 2 2 0 3 1 2 0 0
--------------------
Before pattern replacing
1 3 3 1 3 1 2 1 2 2 0 2 1 2 0 2 2 1 3 0
After pattern replacing
1 3 3 1 3 1 2 1 2 2 0 2 1 2 0 2 2 1 3 0
--------------------
Before pattern replacing
0 0 0 3 2 3 2 2 1 3 2 2 3 1 3 1 1 3 2 0
After pattern replacing
0 0 0 2 3 2 2 1 3 2 2 3 1 3 1 1 3 2 0
--------------------
Before pattern replacing
3 3 1 3 2 2 3 0 3 3 1 1 1 0 0 2 3 3 2 2
After pattern replacing
3 3 1 3 2 2 3 0 3 3 1 1 1 0 0 2 3 3 2 2
--------------------
Press any key to continue . . .