SteveDevin ACM ACG CS CV

DFA

2017-10-08
SteveDevin

最近编译原理课学了DFA, 想起去年暑假学的DFA模式串匹配还没写过, 就趁机写一下了

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;

const int LETTERS = 26;
const int maxn = 200 + 2;

struct TreeNode
{
    TreeNode* child[LETTERS];
    TreeNode* prev;
    bool badNode;

    TreeNode(bool bad = false, TreeNode *p = NULL):badNode(bad), prev(p)
    {
        memset(child, 0, sizeof(child
    }
}Tree[maxn];
int nTreeNode = 0;

void BuildTree(const char *s, TreeNode *p)
{
    for(int i = 0; s[i]; i++)
    {
        if(!p->child[s[i] - 'a'])
            p->child[s[i] - 'a'] = Tree + nTreeNode++;
        p = p->child[s[i] - 'a'];
    }
    p->badNode = true;
}

void BuildDfa(TreeNode *Tree)
{
    for(int i = 0; i < LETTERS; i++)
        Tree[0].child[i] = Tree + 1;
    Tree[0].prev = NULL;
    Tree[1].prev = Tree;

    deque<TreeNode *> q;
    q.push_back(Tree + 1);

    while(!q.empty())
    {
        TreeNode *pRoot = q.front();
        q.pop_front();

        for(int i = 0; i < LETTERS; i++)
        {
            TreeNode *p = pRoot->child[i];
            if(p)
            {
                TreeNode *pPrev = pRoot->prev;
                while(pPrev)
                {
                    if(pPrev->child[i])
                    {
                        p->prev = pPrev->child[i];
                        if(p->prev->badNode) p->badNode = true;
                        break;
                    } else pPrev = pPrev->prev;
                }
                q.push_back(p);
            }
        }
    }
}

bool SearchDfa(TreeNode *Tree, const char *s)
{
    TreeNode *p = Tree + 1;

    for(int i = 0; s[i]; i++)
    {
        while(true)
        {
            if(p->child[s[i] - 'a'])
            {
                p = p->child[s[i] - 'a'];

                if(p->badNode) return true;
                break;
            }else p = p->prev;
        }
    }
    return false;
}

int main()
{
    int N, M;
    cin >> N >> M;

    nTreeNode = 2;

    for(int i = 0; i < N; i++)
    {
        string s;
        cin >> s;
        BuildTree(s.c_str(), Tree + 1);
    }

    BuildDfa(Tree);

    for(int i = 0; i < M; i++)
    {
        string s;
        cin >> s;
        cout << (SearchDfa(Tree, s.c_str()) ? "True" : "False") << endl;
    }

    system("pause");
}

测试结果:

2 2
abc
def
deababcdef
True
deababb
False

写一个可以求出具体位置的版本(正确性待验证):


#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <deque>
using namespace std;

// !!!!  input range in 'a' to 'z'

const int maxn = 200 + 2;
const int LETTERS = 26;

struct TreeNode {
	TreeNode *child[LETTERS];
	TreeNode *prev;
	bool badNode;
	int deep;

	TreeNode() :prev(NULL), badNode(false), deep(0)
	{
		memset(child, 0, sizeof(child));
	}
}Tree[maxn];
int nTreeNode = 0;

void BuildTree(TreeNode *pRoot, char *s)
{
	for (int i = 0; s[i]; i++)
	{
		if (!pRoot->child[s[i] - 'a'])
			pRoot->child[s[i] - 'a'] = Tree + nTreeNode++;
		pRoot->child[s[i] - 'a']->deep = pRoot->deep + 1;
		pRoot = pRoot->child[s[i] - 'a'];
	}
	pRoot->badNode = true;
}

void BuildDfa(TreeNode *Tree)
{
	for (int i = 0; i < LETTERS; i++)
		Tree->child[i] = Tree + 1;
	Tree[0].prev = NULL;
	Tree[1].prev = Tree;

	deque<TreeNode *> q;
	q.push_back(Tree + 1);

	while (!q.empty())
	{
		TreeNode *pRoot = q.front();
		q.pop_front();

		for (int i = 0; i < LETTERS; i++)
		{
			if (pRoot->child[i])
			{
				TreeNode *pPrev = pRoot->prev;
				while (pPrev)
				{
					if (pPrev->child[i])
					{
						pRoot->child[i]->prev = pPrev->child[i];
						if (pRoot->child[i]->prev->badNode)
						{
							pRoot->child[i]->badNode = true;
						}
						break;
					}else pPrev = pPrev->prev;
				}
				q.push_back(pRoot->child[i]);
			}
		}
	}
}

int SearchDfa(TreeNode *Tree, char *s)
{
	TreeNode *p = Tree + 1;
	for (int i = 0; s[i]; i++)
	{
		while (true)
		{
			if (p->child[s[i] - 'a'])
			{
				p = p->child[s[i] - 'a'];
				if (p->badNode) return i - p->deep + 1;
				break;
			}p = p->prev;
		}
	}
	return -1;
}

int main()
{
	int N, M;
	nTreeNode = 2;
	scanf("%d%d", &N, &M);

	char s[maxn];
	for (int i = 0; i < N; i++)
	{
		scanf("%s", s);
		BuildTree(Tree + 1, s);
	}

	BuildDfa(Tree);

	for (int i = 0; i < M; i++)
	{
		scanf("%s", s);
		int ret = SearchDfa(Tree, s);
		if (ret < 0)
			cout << "NOT FOUND" << endl;
		else cout << ret << endl;
	}
}


Comments