⑤AC算法 ? 问题
? 假设词典中有两个词：aba，abcd ? 考虑输入串：bababcdab
? 如何迅速找出输入串中词典词的所有出现？
? 简单解决办法
? 逐字查词典：效率太低
? AC算法
? 将词典构造成一个自动机，一次扫描完成
AC算法构造自动机
- 23 -
8、程序源代码
下面只列出其中的主代码，其他头文件和程序源代码详见电子版目录里的文件。
// dictionDlg.cpp : implementation file #include \#include \#include \#include \#include \#include \#include \#include \
#define MAXSIZE 28220//能够读取的最多单词数，它多于文件中保存的单词数目 #define INCREMENT 5 #ifdef _DEBUG
#define new DEBUG_NEW #undef THIS_FILE
static char THIS_FILE[] = __FILE__; #endif
///////////////////////////////////////////////////////////////////////////// // CAboutDlg dialog used for App About
class CAboutDlg : public CDialog
- 24 -
{
public: CAboutDlg(); // Dialog Data //{{AFX_DATA(CAboutDlg)
enum { IDD = IDD_ABOUTBOX }; //}}AFX_DATA
// ClassWizard generated virtual function overrides //{{AFX_VIRTUAL(CAboutDlg) protected:
virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV support //}}AFX_VIRTUAL
// Implementation protected:
//{{AFX_MSG(CAboutDlg) //}}AFX_MSG
DECLARE_MESSAGE_MAP() };
AWord::AWord(){ //AWORD的构造函数
new CString(WordStr);
new CString(WordMeaning);
}
Dictionary::Dictionary(){//字典类的构造函数 CString rString; int num;
CString pFileName=\存储数据的文件 CStdioFile f1;
f1.Open(\打开文本文件 length=0; ArrayContent=new AWord[MAXSIZE+1];//0号单元未用,用于查询作监视哨 while(f1.ReadString(rString)){ num=++length;
ArrayContent[num].WordStr=rString;//存放读入的单词 f1.ReadString(ArrayContent[num].WordMeaning);//存放其相应的汉语意 }
avalibleSize=MAXSIZE;//可用空间大小，用于以后插入 f1.Close();
}
CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD) { }
//{{AFX_DATA_INIT(CAboutDlg) //}}AFX_DATA_INIT
- 25 -
void CAboutDlg::DoDataExchange(CDataExchange* pDX) {
CDialog::DoDataExchange(pDX); //{{AFX_DATA_MAP(CAboutDlg) //}}AFX_DATA_MAP
}
BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
//{{AFX_MSG_MAP(CAboutDlg) // No message handlers //}}AFX_MSG_MAP
END_MESSAGE_MAP()
9、使用手册
（1）打开diction文件夹，可以看到如下图所示其包含的各个文件。
- 26 -