April 7, 2012, 1:32 am
#include <iostream>
#include <string>
using namespace std;
bool check(string palendrome) {
size_t limit=0;
if(palendrome.size()%2 == 0) limit = palendrome.size()/2;
else limit = (palendrome.size()-1)/2;
for(size_t n=0;n<limit;n++) {
if(palendrome[n] != palendrome[palendrome.size()-n-1]) return false;
}
return true;
}
int main() {
string palendrome1 = "catac";
bool check1 = check(palendrome1); if(check1 == true) cout << palendrome1 << " is palendromic" << endl; else cout << palendrome1 << " is not palendromic" << endl;
string palendrome2 = "caac";
bool check2 = check(palendrome2); if(check2 == true) cout << palendrome2 << " is palendromic" << endl; else cout << palendrome2 << " is not palendromic" << endl;
string palendrome3 = "zcaacr";
bool check3 = check(palendrome3); if(check3 == true) cout << palendrome3 << " is palendromic" << endl; else cout << palendrome3 << " is not palendromic" << endl;
}
April 5, 2012, 5:03 am
I was trying to extract SNMP passwords from a dude data export, I couldn’t actually find them, but the dude password itself is in cleartext… here are the first steps in this process anyway:
1. Export from dude, download the file called backup*.tgz
2. Download and install sqlite3
3. Extract backup data:
3.1 Create the following C++ program, which converts the sqllite blob data to text:
#include <iostream>
#include <fstream>
#include <sstream>
using namespace std;
int main() {
ifstream file("o.txt");
for(;!file.eof();) {
string t;
getline(file,t);
if(file.eof()) break;
size_t startpos=0;
size_t endpos=0;
bool first=true;
for(size_t n=0;n<t.size();n++) {
if(t[n] == '\'') {
if(first) startpos = n+1;
else endpos = n;
first=false;
}
}
t = t.substr(startpos,endpos-startpos);
cout << "output: ";
if(t.size() > 0)
for(size_t n=0;n<(t.size()-1);n+=2) {
string s;
s += t[n];
s += t[n+1];
unsigned int c;
stringstream ss;
ss << std::hex << s;
ss >> c;
cout << string(1,c);
}
cout << endl;
}
}
[/sourcecode]
g++ fileabove.cpp #compile the above code.
The do the following to extract the strings from the blobs:
[sourcecode language="bash"]
mkdir dudebackup
cd dudebackup
cp ../backup*.tgz .
tar xvzf backup*.tgz
~/Downloads/sqlite3 ./dude.db # or wherever sqlite is...
echo '.dump' | ~/Downloads/sqlite3 dude.db > dude.txt
grep objs o > o.txt
./a.out > o.conv
o.conv will then contain a load of blob data. If you grep for “password” you’ll find the dude password. The same password seems to be used to encrypt the login credentials but I haven’t figured out where those are yet.
March 26, 2012, 9:35 pm
Another rough and ready algorithm. Finding the greatest subtree in a binary tree…
Things to remember, values in the tree can be negative so it’s not just the root (sigh).
This implementation is very inefficient. Caching sum in the node makes the efficiency reasonable I believe. But the problem is essentially recursive? Should do some googling to see if there is a better solution.
#include <iostream>
using namespace std;
class Node {
public:
Node () : left(NULL), right(NULL) {}
int value;
int sum;
Node *left;
Node *right;
int getsum() {
sum = 0;
if((left == NULL) && (right == NULL)) return value;
if(left != NULL) sum += left->getsum();
if(right != NULL) sum += right->getsum();
sum += value;
return sum;
}
};
Node *greatestsubtree(Node *current,Node *max) {
if(current == NULL) return max;
int mval = current->getsum();
if(mval > max->getsum()) max = current;
Node *l = greatestsubtree(current->left,max);
Node *r = greatestsubtree(current->right,max);
if(l->getsum() > max->getsum()) max = l;
if(r->getsum() > max->getsum()) max = r;
return max;
}
int main() {
Node *root = new Node();
root->left = new Node();
root->right = new Node();
root->value = 10;
root->left->value = -10;
root->right->value = 5;
root->left->left = new Node();
root->left->left->value = 100;
root->left->right = new Node();
root->left->right->value = 0;
root->right->left = new Node();
root->right->left->value = -8;
cout << root << endl;
cout << greatestsubtree(root,root)->getsum();
}
Version with caching…
#include <iostream>
using namespace std;
class Node {
public:
Node () : left(NULL), right(NULL),sumcache(false) {}
int value;
int sum;
bool sumcache;
Node *left;
Node *right;
int getsum() {
if(sumcache) return sum;
sum = 0;
if((left == NULL) && (right == NULL)) return value;
if(left != NULL) sum += left->getsum();
if(right != NULL) sum += right->getsum();
sum += value;
sumcache = true;
return sum;
}
};
Node *greatestsubtree(Node *current,Node *max) {
if(current == NULL) return max;
int mval = current->getsum();
if(mval > max->getsum()) max = current;
Node *l = greatestsubtree(current->left,max);
Node *r = greatestsubtree(current->right,max);
if(l->getsum() > max->getsum()) max = l;
if(r->getsum() > max->getsum()) max = r;
return max;
}
int main() {
Node *root = new Node();
root->left = new Node();
root->right = new Node();
root->value = 10;
root->left->value = -10;
root->right->value = 5;
root->left->left = new Node();
root->left->left->value = 100;
root->left->right = new Node();
root->left->right->value = 0;
root->right->left = new Node();
root->right->left->value = -8;
cout << root << endl;
cout << greatestsubtree(root,root)->getsum();
}
March 23, 2012, 11:24 pm
Some more rough and ready algorithm code, non-OO C++. Pretty bad code, not well tested, just playing.
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <algorithm>
using namespace std;
class Node {
public:
Node() {
}
vector<Node *> children;
Node *parent;
};
Node *make_random_tree(size_t size,Node *root=NULL) {
if(root == NULL) {
root = new Node();
}
Node *current = root;
size_t children=rand()%size;
for(size_t i=0;i<children;i++) {
Node *nd = new Node();
nd->parent = current;
current->children.push_back(nd);
}
for(size_t n=0;n<current->children.size();n++) {
make_random_tree(size-children,current->children[n]);
}
return root;
}
Node *get_random(Node *root,size_t avg_size) {
Node *current = root;
for(;rand()%(avg_size*2) != 0;) {
if(current->children.size() == 0) return current;
current = current->children[rand()%current->children.size()];
}
return current;
}
Node * get_next_child(Node *node,Node *child) {
bool next=false;
for(size_t n=0;n<node->children.size();n++) {
if(next==true) {
return node->children[n];
}
if(node->children[n] == child) next=true;
}
return NULL;
}
vector<Node *> get_path(Node *root,Node *n) {
vector<Node *> current_path;
current_path.push_back(root);
if(n==root) return current_path;
Node *current_child = root->children[0];
for(;;) {
current_path.push_back(current_child);
if(current_child == n) return current_path;
if(current_child->children.size() != 0) {
current_path.push_back(current_child->children[0]);
current_child = current_child->children[0];
} else {
current_child = NULL;
for(;current_child == NULL;) {
Node *old_child = current_path[current_path.size()-1];
current_path.erase(current_path.begin()+current_path.size()-1,current_path.end());
current_child = get_next_child(current_path[current_path.size()-1],old_child);
if(old_child==root) { return vector<Node *>(); }
}
}
}
// Should never get here
return vector<Node *>();
}
vector<Node *> get_path_parent(Node *root,Node *n) {
vector<Node *> v;
for(Node *current = n;current != root;current = current->parent) {
v.push_back(current);
}
v.push_back(root);
reverse(v.begin(),v.end());
return v;
}
Node *find_lca_parent(Node *root,Node *n1,Node *n2) {
vector<Node *> path1 = get_path_parent(root,n1);
vector<Node *> path2 = get_path_parent(root,n2);
for(size_t n=0;n<path1.size();n++) {cout << path1[n] << " ";} cout << endl;
for(size_t n=0;n<path2.size();n++) {cout << path2[n] << " ";} cout << endl;
size_t shortest_path_length;
if(path1.size() < path2.size()) shortest_path_length = path1.size();
else shortest_path_length = path2.size();
size_t n;
for(n=0;(n<shortest_path_length) && (path1[n] == path2[n]);n++);
return path1[n-1];
}
Node *find_lca(Node *root,Node *n1,Node *n2) {
vector<Node *> path1 = get_path(root,n1);
vector<Node *> path2 = get_path(root,n2);
size_t shortest_path_length;
if(path1.size() < path2.size()) shortest_path_length = path1.size();
else shortest_path_length = path2.size();
size_t n;
for(n=0;(n<shortest_path_length) && (path1[n] == path2[n]);n++);
return path1[n-1];
}
int main() {
Node *root = make_random_tree(100);
Node *n1 = get_random(root,20);
Node *n2 = get_random(root,20);
Node *lca1a = find_lca_parent(root,n1,n2);
Node *lca1b = find_lca (root,n1,n2);
cout << "LCA1-a: " << lca1a << endl;
cout << "LCA1-b: " << lca1a << endl;
Node *n3 = root->children[0]->children[0]->children[0];
Node *n4 = root->children[0]->children[0]->children[1];
Node *lca2a = find_lca_parent(root,n3,n4);
Node *lca2b = find_lca (root,n3,n4);
cout << "LCA2-a: " << lca2a << endl;
cout << "LCA2-b: " << lca2b << endl;
}
RSS