终于用C++实现了AC算法的多模式匹配,代码贴上如下:
//构造ac对象的时候，输入的模式串集合以“end”作为结束标志#include<iostream>#include<vector>#include<string>using namespace std;
//该结构是状态节点,只负责记录当前节点相关的信息class Node{public:char whichCauseToThisStatus;//哪一个动作导致了当前节点的出现int NodeStatus;//当前节点状态int previewNodeStatus;//前一节点状态bool isEndStatus;//是否是终止状态string maxChildString;//该节点串中前面除去第一个字符的最大子串string outputStringOfThisStatus;//如果当前节点是终止节点的话，当前节点应该要输出的内容int whereToGoWhenFailed;//当失配的时候的跳转状态public:Node(){//构造函数setNode(0, -1, false, "", "", -1);}Node(int NS, int PRS, bool IES, string MCS, string OSOTS, int WTGWF){//构造函数setNode(NS,PRS,IES,MCS,OSOTS,WTGWF);}void setNode(int NS, int PRS, bool IES, string MCS, string OSOTS, int WTGWF){NodeStatus = NS;//默认值为根节点previewNodeStatus = PRS;//默认前一个节点的状态是根节点isEndStatus = IES;//默认节点不是终止状态maxChildString = MCS;//默认最大子串为空outputStringOfThisStatus = OSOTS;//当前是输出节点的输出结果whereToGoWhenFailed = WTGWF;//默认跳转是为根节点}friend ostream& operator<<(ostream&cout, Node&n){
cout << "哪一个字符导致了当前的节点:" << n.whichCauseToThisStatus << endl;cout << "当前节点状态:" << n.NodeStatus << endl;cout << "前一个节点状态:" << n.previewNodeStatus << endl;cout << "当前节点是否是终止状态:" << n.isEndStatus << endl;cout << "最大子串:" << n.maxChildString << endl;cout << "如果是终止状态的输出字符串:" << n.outputStringOfThisStatus << endl;cout << "失配的时候应该要回溯到哪里:" << n.whereToGoWhenFailed << endl;return cout;}};
//该结构是每个当前状态indexNode的一次操作结果，可以认为是领域关系, //重要的是要判断该状态下是否存在某操作的结果，如果不存在就添加进去，存在的话就切换当前状态为下一个状态class indexNode{public:int indexStatus;//当前状态char ch;//一次操作int nextStatusOfIndexStatus;//操作结果转移到的状态public:indexNode(){indexStatus = 0;ch = ‘~’;nextStatusOfIndexStatus = 0;}indexNode(int a, char b, int c){indexStatus = a;ch = b;nextStatusOfIndexStatus = c;}void set(int a, char b, int c){indexStatus = a;ch = b;nextStatusOfIndexStatus = c;}bool operator==(const indexNode&iN){return indexStatus == iN.indexStatus&&ch == iN.ch;}bool operator!=(const indexNode&iN){return indexStatus != iN.indexStatus&&ch != iN.ch;}};
//ac算法类class AC{public:vector<Node>vecNode;//vecNode向量存储了各个状态的信息vector<string>vecString;//vecString存储了模式串集合vector<indexNode>vecIndexNode;//存储了状态机的vector,现在的问题是要能够保证能够访问到该vector里面的每一个重复状态，可以使用find函数进行查找public:AC(){//完成模式串集合的输入vecNode.reserve(100);vecString.reserve(20);string s = "";cout << "请输入模式串集合:";while (1){cin >> s;if (s == "end" || s == "END"){break;}vecString.push_back(s);}////输出结果//int k = 0;//for (vector<string>::iterator i = vecString.begin(); i != vecString.end(); i++){//cout <<k<< ","<<vecString[k] << endl;//k++;//}
//AC算法需要处理一下，每个模式串，，从而确定下状态树Node*p = NULL;//p用来新建一个状态string temp;//临时stringint status = 0;//当前状态为0,status只能加加,该状态是新建的状态int tempchar = 0;//对应于一个模式串处理到了哪一个位置int jumpStatus = 0;//跳转状态vector<indexNode>::iterator VINI;//存储0状态vecNode.push_back(Node());for (vector<string>::iterator i = vecString.begin(); i != vecString.end(); i++){//对于每一个模式串
人生的失败往往是在关键时刻少了坚持。
