放出在“至NOI 09有做的事情”里提到的基础代码
http://www.cppblog.com/Files/wwy250/%E5%9F%BA%E7%A1%80%E4%BB%A3%E7%A0%81.rar
由于以后还有机会用到就没有一一测试
但思路一定是正确的
如果发现错误期望提出
里面 trie图错了
这样就对了
#include<iostream>
using namespace std;
struct node
{
bool match;
node *faild,*chaild[26];
}*trie=new node(),*super=new node(),*q[100000];
int h,l;
void insert(node *t,char *c)
{
if(!*c)
{
t->match=1;
return ;
}
if(!t->chaild[*c-'a'])
t->chaild[*c-'a']=new node();
insert(t->chaild[*c-'a'],c+1);
}
void build()
{
for(int i=0;i<26;++i)
super->chaild[i]=trie;
trie->faild=super;
q[l=1]=trie;
for(;h++!=l;)
{
node *p=q[h];
for(int i=0;i<26;++i)
if(p->chaild[i])
{
p->chaild[i]->faild=p->faild->chaild[i];
p->chaild[i]->match|=p->chaild[i]->faild->match;
q[++l]=p->chaild[i];
}
else
p->chaild[i]=p->faild->chaild[i];
}
}
char c[1000];
int match(node *t,int th)
{
if(t->match)
cout<<th<<endl;
if(!c[th])
return 0;
return match(t->chaild[c[th]-'a'],th+1);
}#include<iostream>
using namespace std;
struct node
{
bool match;
node *faild,*chaild[26];
}*trie=new node(),*super=new node(),*q[100000];
int h,l;
void insert(node *t,char *c)
{
if(!*c)
{
t->match=1;
return ;
}
if(!t->chaild[*c-'a'])
t->chaild[*c-'a']=new node();
insert(t->chaild[*c-'a'],c+1);
}
void build()
{
for(int i=0;i<26;++i)
super->chaild[i]=trie;
trie->faild=super;
q[l=1]=trie;
for(;h++!=l;)
{
node *p=q[h];
for(int i=0;i<26;++i)
if(p->chaild[i])
{
p->chaild[i]->faild=p->faild->chaild[i];
p->chaild[i]->match|=p->chaild[i]->faild->match;
q[++l]=p->chaild[i];
}
else
p->chaild[i]=p->faild->chaild[i];
}
}
char c[1000];
int match(node *t,int th)
{
if(t->match)
cout<<th<<endl;
if(!c[th])
return 0;
return match(t->chaild[c[th]-'a'],th+1);
}
树状数组里ask的变量名打错了
正确的应是
#include<iostream>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
int c[1000001],n;
inline void add(int p,int v)
{
for(int i=p;i<=n;i+=lowbit(i))
c[i]+=v;
}
inline int ask(int p)
{
int r=0;
for(int i=p;i>0;i-=lowbit(i))
r+=c[i];
return r;
}
posted on 2009-03-09 03:57
250 阅读(730)
评论(0) 编辑 收藏 引用 所属分类:
oi