UVALive 4811 Growing Strings【AC自动机+简单dp】

AC自动机
给出n个字符串，问最多能够选出多少个串组成序列，并满足前一个字符串是后一个字符串的子串。
这个和上一题类似，但是更加简单。
对于AC自动机，我们知道的是，父亲节点是它所以儿子节点的前缀，$fail[i]$节点是$i$节点的后缀，因此都是它的子串。
那么我们可以考虑dp的情况。
$$dp[u]=max(dp[fa[u]],dp[fail[u]])+end[u]$$
其中end[u]表示，以u节点结尾的单词有多少。
然后取出dp数组中的最大值就是答案。

//      whn6325689
//      Mr.Phoebe
//      http://blog.csdn.net/u013007900
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;
#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<50
#define speed std::ios::sync_with_stdio(false);typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair pll;
typedef complex point;
typedef pair<int, int> pii;
typedef pairint> piii;
typedef vector<int> vi;#define CLR(x,y) memset(x,y,sizeof(x))
#define CPY(x,y) memcpy(x,y,sizeof(x))
#define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
#define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
#define debug(a) cout << #a" = " << (a) << endl;
#define debugarry(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))#define MID(x,y) (x+((y-x)>>1))
#define getidx(l,r) (l+r | l!=r)
#define ls getidx(l,mid)
#define rs getidx(mid+1,r)
#define lson l,mid
#define rson mid+1,rtemplate<class T>
inline bool read(T &n)
{T x = 0, tmp = 1;char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
template <class T>
inline void write(T n)
{if(n < 0){putchar('-');n = -n;}int len = 0,data[20];while(n){data[len++] = n%10;n /= 10;}if(!len) data[len++] = 0;while(len--) putchar(data[len]+48);
}
//-----------------------------------const int MAXN=1000010;
const int MAC=26;int n;
char str[MAXN];struct AC
{int ch[MAXN][MAC],f[MAXN],size;int end[MAXN],fa[MAXN];int dp[MAXN];void init(){size=f[0]=0;newnode(0);}int newnode(int pre){CLR(ch[size],0);fa[size]=pre;end[size]=0;dp[size]=0;return size++;}void insert(char *S){int u=0,x;for(char *sp=S;*sp;sp++){x=*sp-'a';if(!ch[u][x])   ch[u][x]=newnode(u);u=ch[u][x];}end[u]++;}int que[MAXN],front,back;int getfail(){int u,cur,ans=-1;front=back=0;for(int i=0;iif(ch[0][i]){que[back++]=ch[0][i];f[ch[0][i]]=0;dp[ch[0][i]]=end[ch[0][i]];ans=max(ans,dp[ch[0][i]]);}while(frontfor(int i=0;iif(u){que[back++]=u;f[u]=ch[f[cur]][i];}elsech[cur][i]=ch[f[cur]][i];dp[u]=max(dp[fa[u]],dp[f[u]])+end[u];ans=max(ans,dp[u]);}} return ans;}
}ac;int main()
{while(read(n)&&n){ac.init();for(int i=1;i<=n;i++){scanf("%s",str);ac.insert(str);}printf("%d\n",ac.getfail());}return 0;
} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！