简易英汉词典

⑤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 -