放出在“至NOI 09有做的事情”里提到的基礎(chǔ)代碼
http://m.shnenglu.com/Files/wwy250/%E5%9F%BA%E7%A1%80%E4%BB%A3%E7%A0%81.rar
由于以后還有機(jī)會(huì)用到就沒(méi)有一一測(cè)試
但思路一定是正確的
如果發(fā)現(xiàn)錯(cuò)誤期望提出
里面 trie圖錯(cuò)了
這樣就對(duì)了
#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);
}
樹(shù)狀數(shù)組里ask的變量名打錯(cuò)了
正確的應(yīng)是
#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 閱讀(753)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
oi