通用文本算法库的设计毕业论文.doc

通用文本算法库的设计毕业论文 目 录 第一章 工程结构说明 1 第二章 源程序头文件 2 Base.h 2 Queue.h 2 ExactMatchingS.h 3 Automata.h 4 ExactMatchingM.h 5 RegularExpression.h 5 SuffixArray.h 7 ExtendKMP.h 8 DES.H 8 DoubleHash.h 10 第三章 源程序代码文件 12 ExactMatchingS.cpp 12 ExactMatchingM.cpp 20 Automata.cpp 23 RegularExpression.cpp 26 SuffixArray.cpp 33 DES.cpp 39 DoubleHash.cpp 45 ExtendKMP.cpp 47 第一章 工程结构说明 整个工程由10个头文件以及8个源文件组成，可在Visual C++或者GCC下编译。头文件中含有所有的函数声明，而源文件中则是所有函数的具体实现。 该工程的结构如下图所示： 第二章 源程序头文件 Base.h //Base.h //头文件包含及基础数据结构，头文件 //by 赵扶摇 #include iostream #include algorithm #include functional #include queue #include cstdio #include cstdlib #include cstring #include cmath #include list #include vector #include iostream #include fstream using namespace std; #define MAX_RANGE 256 #define MAX_PATTERN_LENGTH 1024 #define MAX_TEXT_LENGTH 100000 #define MAX_LOGN 20 #define FAIL -1 #define EPSILON 1 #define MAX_REP 50 #define MACHINE_WORD_LENGTH 32 #define LOG_2 0.693147 //ln(2)的大小 #define log_2(a) (int)(log((double)(a)) / LOG_2) #define newArray(type, p, size, val) {(p) = new type[(size)]; memset(p,(val),sizeof(type)*(size));} Queue.h //Queue.h //队列，头文件 //by 赵扶摇 #pragma once typedef struct { int curr; int parent; char label; } QueueNode; //专用队列节点 #define EnQueue(Q) ((Q[rear++])) //取得要记录的节点 #define DeQueue(Q) ((Q[front++])) #define EmptyQueue() (rear == front) #define InitQueue(Q, size) {Q = new QueueNode[(size)]; rear = front = 0;} ExactMatchingS.h //ExactMatchingS.h //多串精确模式匹配，头文件 //by 赵扶摇 #pragma once #include Base.h //Shift-And算法 void ShiftAnd(char *t, char *p, int n, int m, int res[], int cnt); //ShiftOr算法 void ShiftOr(char *T, char *P, int n, int m, int res[], int cnt); //暴力算法 void Naive(char *t, char *p, int n, int m, int res[], int cnt); //RabinKarp算法 void RabinKarp(char *t, char *p, int n, int m, int res[], int cnt); //更快的RabinKarp匹配版本 void RabinKarpFaster(char *t, char *p, int n, int m, int res[], int cnt); //自动机的建立 void Build_DFA(char *P, int m, int trans[][MAX_PATTERN_LENGTH]); //使用前向自动