String Searching
A. First Edition
This is second edition of code competition problem 1 which I try to use my DFSArray class to solve. So, it is
also an improved edition of my DFS class. (How many editions have been made for DFS? I don't remember.)
It is the same old trick--To setup a series of options and at each node test these options. However, I thought
I run into unsolvable obstacles at first. You see, "abcdab", for example, there are two "ab" at different postion.
Then it means for option "ab", there exists two result! But my "validateOptions" function only return true or false.
How can I recognize there are actually TWO different results derived from same option---"ab"? It seems a contradictive
to TURING Machine---for one input there should be one definite output. However, there is a way to solve it! Because
there is different state inside class. See the pointer is at different positions of string, so, it means a different
states can be tracked. I add an internal data member--state to indicate the position of pointer in string. When
the positions are different, we must traverse all choices again.
1. void StrSearching::trackString()
This is quite like the old "backTrack" function and save "curString" instead of "choices" in an array.
2. bool StrSearching::validateOption(int sonData)
First you should make sure there is an matching choice, then try to make sure there is no repeating result in
upper nodes. (Note that different choices may lead to same result, but we only care about results instead of
"choices" here.£©
£³£®void StrSearching::readFile(const char* fileName)
This function read rules into a 2-dimension array, and initial string and target string also at end of this array.
4. bool DFS::beginCount(int max, bool findall)
This function was changed a little bit to fix the logic loophole: I should always evaluate first for any node
before trying to generate new nodes from it. And whenever a node touch down, it should return to try next node.
5. char* StrSearching::replaceStr(char* source, char* target, int start, int size)
A utility function to insert a target string into source with starting position at start and replaced string length
is size. Do you understand? Surely it is easy to read code.
E.Further improvement
1. The change in this version of DFS is considered to be a rather big one. Should I standardize it as lib? I doubt it.
””
//file DFS.h
#ifndef DFS_H
#define DFS_H
#include <iostream>
using namespace std;
const int MaxSonCount=8;
const int MaxLevel = 120;
const int MaxOptions = 16;
const int MaxNodeCount = 300;
class DFS
{
private:
void initialize(DFS* now);
static bool initialized;
static DFS* nodeList[MaxNodeCount];
static bool findAll;
static int optionArray[MaxOptions];
static int optionCount;
static char** nameString;
static int solutionCount;
static int maxLevel;
void addSon(int sonData);
bool touchDown();
void setMaxLevel(int max) { maxLevel = max;}
DFS* upDate();
static int domino;
bool hasBrother();
DFS* nextBrother();
bool generate();
DFS* findNext();
void putNode(int theIndex) { nodeList[theIndex] = this;}
protected:
int state;
int stateCount;
int parent;
int sonCount;
int sonIndex;
int son;
int depth;
int index;//index in nodeList
int data;
static int trackRecord[MaxLevel];
void backTrack();
DFS* getNode(int theIndex){return nodeList[theIndex];}
DFS* getParent(){return getNode(parent);}
bool hasParent(){return parent!=-1;}
virtual void setStateCount();
virtual void onAfterAdded();
virtual void onGenerate();
virtual void onBeginSearch();
virtual DFS* createSon() = 0;
virtual bool validateOption(int sonData) =0; //made it pure virtual
virtual void onLeave();
virtual bool evaluate() = 0;
virtual void collectResult();
public:
int getSolutionCount(){ return solutionCount;}
void setOptions(int* array, int size);
void setNameStr(char** str){nameString = str;}
bool beginCount(int max, bool findall=false);
virtual ~DFS();//virtual destructor
};
#endif
””
//file DFS.cpp
#include <iostream>
#include "DFS.h"
using namespace std;
int DFS::domino = 0;
bool DFS::findAll = false;
bool DFS::initialized = false;
int DFS::maxLevel = 0;
int DFS::optionArray[MaxOptions] = {0};
char** DFS::nameString=NULL;
int DFS::solutionCount = 0;
int DFS::optionCount = 0;
DFS* DFS::nodeList[MaxNodeCount] = {NULL};
int DFS::trackRecord[MaxLevel]= {0};
bool DFS::touchDown()
{
return depth==maxLevel;
}
void DFS::onBeginSearch()
{
//programmer may need do some initializing job here!
}
//user can synchronize sonNode and fatherNode
void DFS::onAfterAdded()
{
//programmer may need do something for his own purpose
}
void DFS::onLeave()
{
DFS* ptr =this;
if (ptr->hasParent())
{
DFS* father = ptr->getParent();
domino -= father->sonCount;
father->sonCount = 0;
father->son = -1;
}
}
void DFS::backTrack()
{
DFS* ptr = this;
while (ptr->hasParent())
{
trackRecord[ptr->depth-1] = ptr->data;
ptr = ptr->getParent();
}
}
//a stack
void DFS::collectResult()
{
backTrack();
cout<<"The route is:\n";
for (int i=0; i<depth; i++)
{
cout<<nameString[trackRecord[i]]<<", ";
}
cout<<"\nIt is number:"<<solutionCount++;
cout<<endl;
}
void DFS::setOptions(int *array, int size)
{
optionCount = size;
for (int i=0; i<size; i++)
{
optionArray[i] = *(array+i);
}
}
DFS::~DFS()
{
if (initialized)
{
for (int i=1; i<MaxNodeCount; i++)//the i=0 is root which is not dynamic allocated!
{
delete nodeList[i];
}
domino =0;
initialized=false;
}
}
void DFS::onGenerate()
{
//programmer may need to initialize at this stage
}
bool DFS::beginCount(int max, bool findall)
{
DFS* ptr = this;
setMaxLevel(max);
findAll = findall; //setup if want all result
initialize(this);
onBeginSearch();//this is done from root!
while (ptr!=NULL)
{
if (ptr->evaluate())
{
ptr->collectResult();
if (!findAll)
{
break;
}
else
{
ptr = ptr->findNext();
}
}
if (ptr->touchDown())//for a new son
{
ptr=ptr->findNext();
}
//programmer may need to initialize at this stage
ptr->onGenerate();
if (ptr->generate())
{
ptr = ptr->upDate();//move to first son
}
else
{
ptr = ptr->findNext();//for a new son
}
}
if (solutionCount==0)
{
cout<<"no solution!";
return false;
}
else
{
cout<<"Total solution is "<<solutionCount<<endl;
return true;
}
}
DFS* DFS::findNext()
{
DFS* ptr = this;
DFS* dummy;
while (ptr!=NULL)
{
if (ptr->hasBrother())
{
ptr = getNode(ptr->index+1);//next brother
return ptr;
}
else
{
if (ptr->hasParent())
{
dummy = ptr;
ptr = ptr->getParent(); //if
dummy->onLeave(); //only clear when go up one level
}
else
{
break;
}
}
}
return NULL;
}
void DFS::setStateCount()
{
//user should specify here what kind of internal state number it is.
}
bool DFS::generate()
{
bool result = false;
if (touchDown())
{
return false;
}
stateCount =1;
setStateCount();
for (state =0; state<stateCount; state++)
{
//this is preorder and I don't bother to
//give choices for midorder or postorder
for (int i=0; i< optionCount; i++)
{
if (validateOption(optionArray[i]))
{
addSon(optionArray[i]);
result = true;
}
}
}
return result;
}
DFS* DFS::upDate()
{
//return first son
return getNode(son);
}
void DFS::addSon(int sonData)
{
if (sonCount+1<MaxSonCount)
{
if (domino==MaxNodeCount)
{
cout<<"Exceeds limit of node list"<<endl;
return;
}
//DFS* ptr = createSon();
DFS* ptr = nodeList[domino];
ptr->index = domino;//
//ptr->putNode(domino);
if (sonCount==0)//if it is the first son
{
son = domino;//first son
}
domino++;
ptr->state = state;
ptr->stateCount = stateCount;
ptr->data = sonData;
ptr->sonCount = 0;
ptr->son = -1;//temporarily
ptr->parent = index;
ptr->depth = depth+1;
ptr->sonIndex = sonCount;
sonCount++;
ptr->onAfterAdded();
}
else
{
cout<<"Exceed max of sons!";
}
}
void DFS::initialize(DFS* now)
{
now->index =0;
now->depth = 0;
now->sonCount = 0;
now->sonIndex = -1;
now->parent = -1;
now->data = 0;
now->son = -1;
now->putNode(0); //put in list
if (!initialized)
{
for (int i=1; i<MaxNodeCount; i++)
{
nodeList[i] = createSon();
}
initialized = true;
}
domino++;
}
bool DFS::hasBrother()
{
if (hasParent())
{
if (getParent()->sonCount > sonIndex+1)//has little brother
{
return true;
}
}
return false;
}
//file StringSearch.cpp
#include <iostream>
#include "DFS.h"
#include <fstream>
using namespace std;
const int MaxRuleNum=10;
class StrSearching: public DFS
{
private:
static int ruleNum;
static char* ruleString[2][MaxRuleNum];
static char* records[MaxLevel];
char* createString(const char* input);
char* curString;
static int options[MaxRuleNum];
char* replaceStr(char* source, char* target, int start, int size);
void trackString();
protected:
virtual bool validateOption(int sonData);
virtual DFS* createSon();
virtual void setStateCount();
virtual bool evaluate();
virtual void collectResult();
virtual void onBeginSearch();
virtual void onAfterAdded();
virtual void onLeave();
public:
void readFile(const char* fileName);
virtual ~StrSearching();
};
char* StrSearching::records[MaxLevel];
int StrSearching::ruleNum = 0;
char* StrSearching::ruleString[2][MaxRuleNum];
int StrSearching::options[MaxRuleNum]={0};
int main()
{
StrSearching S;
S.readFile("c:\\strSearch.txt");
S.beginCount(20, true);
return 0;
}
void StrSearching::trackString()
{
StrSearching* ptr = this;
while(ptr!=NULL)
{
records[ptr->depth] = ptr->curString;
if (ptr->hasParent())
{
ptr = (StrSearching*)ptr->getParent();
}
else
{
break;
}
}
}
StrSearching::~StrSearching()
{
// delete []curString;
}
char* StrSearching::replaceStr(char* source, char* target, int start, int size)
{
int targetSize = strlen(target);
int newSize = strlen(source) + targetSize -size;
char* result = new char[newSize+1];
for (int i=0; i<=newSize; i++)//copy null
{
if (i<start)
{
result[i]= source[i];
}
else
{
if (i<start+targetSize)
{
result[i] = target[i-start];
}
else
{
result[i] = source[i-targetSize+size];
}
}
}
return result;
}
void StrSearching::onLeave()
{
StrSearching* ptr = (StrSearching*)getParent();
StrSearching* sonPtr;
if (ptr!=NULL)
{
for (int i=0; i< ptr->sonCount; i++)
{
sonPtr = (StrSearching*)(getNode(ptr->son+i));
delete []sonPtr->curString;
}
}
DFS::onLeave();
}
bool StrSearching::validateOption(int sonData)
{
char* pStr;
StrSearching* ptr = this;
if (strncmp(curString+state, ruleString[0][sonData], strlen(ruleString[0][sonData]))==0)
{
pStr = replaceStr(curString, ruleString[1][data], state, strlen(ruleString[0][data]));
trackString();
for (int i=0; i<=depth; i++)
{
if (strcmp(records[i], pStr)==0)
{
delete []pStr;
return false;
}
}
delete []pStr;
return true;
}
return false;
}
void StrSearching::onAfterAdded()
{
curString = replaceStr(((StrSearching*)(getParent()))->curString, ruleString[1][data],
state, strlen(ruleString[0][data]));
}
void StrSearching::onBeginSearch()
{
curString = createString(ruleString[0][ruleNum]);
}
bool StrSearching::evaluate()
{
return strcmp(curString, ruleString[1][ruleNum])==0;
}
void StrSearching::collectResult()
{
cout<<"A solution\n";
trackString();
for (int i=0; i<=depth; i++)
{
cout<<records[i]<<endl;
}
}
void StrSearching::readFile(const char* fileName)
{
ifstream in(fileName, ios::in);
char buffer[2][20];
in>>ruleNum;
for (int i=0; i< ruleNum+1; i++)
{
in>>buffer[0]>>buffer[1];
ruleString[0][i] = createString(buffer[0]);
ruleString[1][i] = createString(buffer[1]);
options[i] = i;//0,1,2...
}
setOptions(options, ruleNum);
}
DFS* StrSearching::createSon()
{
DFS* ptr = new StrSearching;
return ptr;
}
char* StrSearching::createString(const char* input)
{
char* result = new char[strlen(input)+1];
if (result==NULL)
{
cout<<"Unable allocate memory!\n";
}
else
{
strcpy(result, input);
}
return result;
}
void StrSearching::setStateCount()
{
stateCount = strlen(curString);
}
””
Running result of program:
You may notice in the solution of Code Competition 1, that "big master" suggest a breadth-first-search, cause it
will give you shortest answer for sure. Indeed, but a "max level" restricted "depth-first-search" will give you same
result as expected. And you can see there is one more solutions!
A solution abab baab babcd bbcdcd bbad bbabb bbbab bbbba A solution abab baab babcd bbcdcd bbcdcbb bbabb bbbab bbbba A solution abab baab babcd babcbb bbcdcbb bbabb bbbab bbbba A solution abab abbcd babcd bbcdcd bbad bbabb bbbab bbbba A solution abab abbcd babcd bbcdcd bbcdcbb bbabb bbbab bbbba A solution abab abbcd babcd babcbb bbcdcbb bbabb bbbab bbbba A solution abab abbcd abbcbb babcbb bbcdcbb bbabb bbbab bbbba