SPOJ 7758 Growing Strings (AC自动机)

给出n个串,选出若干个串排成一行,保证前一个是后一个的前缀或者后缀,求最多能选出多少个串满足条件。

公共前缀其实就是在字典树上遍历根到叶子的路径,公共后缀可以通过fai指针来搞。dp[u]表示AC自动机上节点u为结尾能够选的最多串的个数,dp[v] = max(dp[u], dp[fail[v]]) + cnt[v],v是u的后继节点,这个可以在构建自动机fail指针的同时搞出来。

 

LEAVE A COMMENT