Trie based string match
最近经常遇到WinEdt dvi->pdf文件过程出现 error unable to open “*.pdf” 的错误，然后我一般都是打开资源管理器，然后找到这个文件对应的句柄，然后把对应的process kill掉，
不知道大家有没有更好的解决方案。
之前这道题目一直掐在这里，当时是偶然看到vjudge这个融合几个OJ的一个神奇OJ，然后一个HUST的学弟给我发的链接。
但是第一道题目发现比Trie的裸题稍微加了点东西，之前有一个大致的朴素算法也是每个后缀去match这个字典树，但是当时好像是发现这个做法对于是否能够处理keyword之间有前缀关系
产生了怀疑还是什么，然后就停在那里，没有继续做了。
后来发给瞿神，瞿神也是这个思路，但是没A。
最后还是在光环无限的fawkes大神的指导下，A了这道题目。首先答案是0~N的范围，N是keyword数这点和题意是契合的，但是fawes大神考虑到keyword是否可能出现重复，于是就要稍微改改代码了。果然在大神指导下A了这道题目。
附上代码：里面有几个地方的改进是在大神指导下完成的。
首先传后缀只要传入一个指针，这样的话就需要转成char 传进去，但是c_str()是const char 要注意。
然后之前有个bug就是遍历trie的指针，和query 字符串的遍历都要考虑是否越界，我当时以为肯定trie先遍历完，于是query不会越界，但是后来发现其实字符串如果trie里有一个keyword是query的前缀，
那么就会出现字符串先越界，所以要特别当心，这个还是代码经验不够丰富导致的，我一眼还看不出bug，超珲立马就看出来了。然后就是判断字符串是否越界，用了strlen，但是大神强调这是O(n)，用判断是否\0处理，同时当时写的快了，漏了一个bool 非来判断字符串遍历结束。
如果是处理keyword重复的话，就是每个count含义和之前自己定义的不同了，之前是为了计算匹配了前缀的keyword数方便，在构建trie的时候，就每次往下一个keyword当前count就
++，计算的是子树里keyword的个数。现在是当前keyword在字典里有几个。于是再每次遍历完一个keyword的时候，就将其count++就可以了，两个for循环只要第一个for结束之后count++就可以了，表示最后一个节点的count++，正好对应了keyword的count。
5.还有一个细节也是代码不熟练，我一直纠结如何避免重复的匹配，以为题目keyword只有是否出现的概念，多个keyword也是如此，超珲大神用isword=false来加锁，这样第一次count累加了之后之后再match就不会多累加了。然后ans全局变量作为累加值，其实主要是这个加锁的思想没有立马反应过来。
按照瞿神的说法，这道题目的数据不够强，如果强的话，需要AC自动机，虽然我还不会。。。
http://vjudge.net/contest/view.action?cid=50652#problem/F
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
struct node
{
bool isword;
node* child[26];
int count;
node()
{
for(int i=0;i<26;i++)
child[i]=NULL;
isword=false;
count=0;
}
};
node root;
string dict[10000];
int n,m;
string query;
void CreateTrie()
{
root.isword=false;
for(int i=0;i<26;i++)
root.child[i]=NULL;
for(int i=0;i<n;i++)
{
node* p=&root;
for(int j=0;j<dict[i].size();j++)
{
node*& pchild=p->child[dict[i][j]-'a'];
if(pchild)
{
//pchild->count++;
p=pchild;
}
else
{
pchild=new node;
pchild->isword=false;
//pchild->count=1;
p=pchild;
}
}
p->isword=true;
p->count++;
}
}
/*
int GetCount()
{
for(int start=0;start<query)
node* p=&root;
for(int i=0;i<query.size();i++)
{
if(p->child[query[i]-'a']!=NULL)
p=p->child[query[i]-'a'];
else
return 0;
}
return p->count;
}
*/
//bool keyindesc[n];//initaial false;
int ans;
void find(const char* query)
{
node* p=&root;
int stri=0;
do
{
if(!query[stri])
break;
p=p->child[query[stri++]-'a'];
if(p && p->isword)
{
p->isword=false;
ans+=p->count;
}
}while(p);
}
int main()
{
//freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
ans=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
cin>>dict[i];
CreateTrie();
cin>>query;
const char* cstr=query.c_str();
for(int starti=0;starti<query.size();starti++)
{
find(cstr+starti);
}
printf("%d\n",ans);
}
return 0;
}
然后几天看了下瞿神的matrix store的 trie，万物都是图。同时memset(ch[0],-1, sizeof(ch[0]));
这种写法其实是-1 变成32bit1，然后初始化ch[0]指向的30个int，sizeof(ch[0])其实是不如sizeof(int)*30, 因为传入函数可能数组名退化为指针，当然一般使用全局的都没有太大的差别。