巷北

orz 各位神犇

sam合辑

LCS:裸题直接上。

LCS2:拿每个串去匹配,得到每个结点的最大的答案。
对每个结点取每次匹配的最小值。同时用用每个结点更新pre
答案是每个结点答案去max

bzoj 2555:对每个np记1,然后暴力更新pre(强制在线= =)
然后询问,暴力匹配,失败就是0,成功就是这个点的sz(孩子包括自己的np个数)

bzoj 3988:T=0,每个结点记为1,求个子树和,多了下一位,不多向下(像主席树)
T=1,val[pre] += val[x],同T=0

spojSUBLEX:同3998 T = 0

hdu3518:给代表主串的len个字符l=r=i,用x更新pre,相当于记录每个串的最早出现位置,最迟出现位置,如果每个点的r-l>pre.len,那么长度在min(r-l,lenx)到pre.len+1的之间的都可以成为答案。

hdu4436:多串的建立,每次新串就把last = root,插入一个结点时,如果必须要 !last[s[i]] || ch[last][s[i]] . len != i 才插入这个结点。然后做一遍树p就可以了。

hdu4416,拿每个串去跟主串匹配,求每个结点的max,用结点len键下就行,表示只有大于才不会出现重复

bzoj4032 http://jiruyi910387714.is-programmer.com/posts/90425.html