hdu 4117 GRE Words （ac自动机线段树 dp）

此题利用了ac自动机fail树的性质，fail指针建立为树，表示父节点是孩子节点的后缀

然后更新其影响的字符串的方法，即区间更新，维护最大值，用线段树优化。

而其可以影响的字符串为其在fail树中的子树节点

此题一直MLE，调了一下午+晚上。最后发现。

（1）ac自动机中的节点开始直接初始化，应动态初始化（也终于理解了许多人那么做）

（2）还有用vector表示树边时，一开始初始clear，也会耗很多内存。

（3）线段树开始直接初始化CLR（smax， 0）CLR（cov， 0），由于数组比较大，内存耗较大

最后，ac自动机节点动态初始化，用链表模拟表示树边，线段树动态build，终于有MLE变成了wa

怒重敲，终于ac了

PS:一开始使用后缀数组ac的，数据水了。。。

不过ac自动机2s+，后缀数组8s+

ac自动机：

#pragma comment(linker, /STACK:1024000000,1024000000)
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include
           #include 
           
             #include 
            
              #include 
             
               #include 
              
                using namespace std; #define FE(i, a, b) for(int i = (a); i <= (b); ++i) #define FD(i, b, a) for(int i = (b); i >= (a); --i) #define REP(i, N) for(int i = 0; i < (N); ++i) #define CLR(a, v) memset(a, v, sizeof(a)) #define PB push_back #define MP make_pair typedef long long LL; const int INF = 0x3f3f3f3f; #define lson l, m, rt << 1 #define rson m + 1, r, rt << 1 | 1 const int MAX = 333333; const int SIG = 26; struct Edge{ int to, next; }adj[MAX * 2]; int adj_cnt; int head[MAX]; void adj_init() { adj_cnt = 0; CLR(head, -1); } void add_edge(int x, int y) { adj[adj_cnt].to = y; adj[adj_cnt].next = head[x]; head[x] = adj_cnt++; } int tl[MAX], tr[MAX]; int tot; char ca[MAX], s[MAX]; int id[MAX]; int val[MAX]; int smax[MAX << 2], cov[MAX << 2]; void update_cov(int rt, int x) { smax[rt] = max(smax[rt], x); cov[rt] = max(cov[rt], x); } void up(int rt) { smax[rt] = max(smax[rt << 1], smax[rt << 1 | 1]); } void down(int rt) { if (cov[rt]) { update_cov(rt << 1, cov[rt]); update_cov(rt << 1 | 1, cov[rt]); cov[rt] = 0; } } void build(int l, int r, int rt)///!!! { smax[rt] = cov[rt] = 0; if (l == r) return ; int m = (l + r) >> 1; build(lson); build(rson); up(rt); } void update(int L, int R, int x, int l, int r, int rt) { if (L <= l && r <= R) { update_cov(rt, x); return ; } down(rt); int m = (l + r) >> 1; if (L <= m) update(L, R, x, lson); if (R > m) update(L, R, x, rson); up(rt); } int query(int p, int l, int r, int rt) { if (l == r) return smax[rt]; down(rt); int m = (l + r) >> 1; if (p <= m) return query(p, lson); else return query(p, rson); } struct AC{ int ch[MAX][SIG]; int f[MAX]; int sz; int newnode()///!!! { CLR(ch[sz], 0); return sz++; } void init() { sz = 0; newnode(); } int idx(char c) { return c-'a'; } void insert(char *s) { int u=0,n=strlen(s); for(int i=0;i
               
                 q; f[0] = 0; for(int c = 0; c < SIG; c++) { int u = ch[0][c]; if(u) { f[u] = 0; q.push(u); } } while(!q.empty()) { int r = q.front(); q.pop(); for(int c = 0; c < SIG; c++) { int u = ch[r][c]; if(!u) { ch[r][c] = ch[f[r]][c]; continue; } q.push(u); int v = f[r]; while(v && !ch[v][c]) v = f[v]; f[u] = ch[v][c]; } } } void dfs(int u, int fa) { tl[u] = ++tot; for (int r = head[u]; r != -1; r = adj[r].next) { int v = adj[r].to; if (v != fa) dfs(v, u); } tr[u] = tot; } void makeTree() { adj_init(); for (int i = 1; i < sz; i++)/// { add_edge(i, f[i]); add_edge(f[i], i); } tot = 0; dfs(0, -1); } int solve(char *s) { int len = strlen(s); int u = 0; int now, ans; ans = now = 0; build(1, tot, 1); for (int i = 0; i < len; i++) { u = ch[u][s[i] - 'a']; int valu = query(tl[u], 1, tot, 1); now = max(now, valu); if (id[i]) { if (val[id[i]] > 0) now += val[id[i]]; ans = max(ans, now); update(tl[u], tr[u], now, 1, tot, 1); u = now = 0; } } return ans; } }ac; int main() { int len; int n, m; int T, nc; nc = 1; scanf(%d, &T); while (T--) { scanf(%d, &n); len = 0; ac.init(); CLR(id, 0); for (int i = 1; i <= n;i++) { scanf(%s%d, ca, &val[i]); ac.insert(ca); int l = strlen(ca); REP(j, l) { s[len++] = ca[j]; } id[len - 1] = i; } ac.getFail(); ac.makeTree(); printf(Case #%d: %d , nc++, ac.solve(s)); } }

后缀数组：

//#pragma warning (disable: 4786)
//#pragma comment (linker, /STACK:16777216)
//HEAD
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include
           #include 
           
             #include 
            
              #include 
             
               #include 
              
                using namespace std; //LOOP #define FF(i, a, b) for(int i = (a); i < (b); ++i) #define FD(i, b, a) for(int i = (b) - 1; i >= (a); --i) #define FE(i, a, b) for(int i = (a); i <= (b); ++i) #define FED(i, b, a) for(int i = (b); i>= (a); --i) #define REP(i, N) for(int i = 0; i < (N); ++i) #define CLR(A,value) memset(A,value,sizeof(A)) #define CPY(a, b) memcpy(a, b, sizeof(a)) #define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++) //STL #define SZ(V) (int)V.size() #define PB push_back //INPUT #define RI(n) scanf(%d, &n) #define RII(n, m) scanf(%d%d, &n, &m) #define RIII(n, m, k) scanf(%d%d%d, &n, &m, &k) #define RIV(n, m, k, p) scanf(%d%d%d%d, &n, &m, &k, &p) #define RV(n, m, k, p, q) scanf(%d%d%d%d%d, &n, &m, &k, &p, &q) #define RS(s) scanf(%s, s) //OUTPUT #define WI(n) printf(%d , n) #define WS(s) printf(%s , s) typedef long long LL; typedef unsigned long long ULL; typedef vector 
               
                 VI; const int INF = 1000000000; const double eps = 1e-10; const int MAXN=110000 * 4; int wa[MAXN], wb[MAXN], wv[MAXN], wn[MAXN]; char r[MAXN]; int a[MAXN], sa[MAXN], rank[MAXN], height[MAXN]; int idx[MAXN]; int val[20010]; int len[20010]; int sumlen[20010]; int dp[20010]; int cmp(int *r, int a, int b, int k) { return r[a] == r[b] && r[a + k] == r[b + k]; } void build_sa(int *r, int *sa, int n, int m) { int i, j, p; int *x = wa, *y = wb, *t; for (i = 0; i < m; i++) wn[i] = 0; for (i = 0; i < n; i++)wn[x[i] = r[i]]++;/// for (i = 1; i < m; i++) wn[i] += wn[i - 1]; for (i = n - 1; i >= 0; i--) sa[--wn[x[i]]] = i; for (p = 1, j = 1; p < n; j <<= 1, m = p) { for (p = 0, i = n - j; i < n; i++) y[p++] = i; for (i = 0; i < n; i++) if (sa[i] >= j) y[p++] = sa[i] - j; for (i = 0; i < m; i++) wn[i] = 0; for (i = 0; i < n; i++) wn[wv[i] = x[y[i]]]++;/// for (i = 1; i < m; i++) wn[i] += wn[i - 1]; for (i = n - 1; i >= 0; i--) sa[--wn[wv[i]]] = y[i]; t = x; x = y; y = t; x[sa[0]] = 0; p = 1; for (i = 1; i < n; i++) x[sa[i]] = cmp(y, sa[i - 1], sa[i], j)   p - 1 : p++; } } void getHeight(int *r, int *sa, int n) { int i, j, k = 0; for (i = 1; i <= n; i++) { rank[sa[i]] = i; height[i] = 0; } for (i = 0; i < n; i++) { if (k) k--; j = sa[rank[i] - 1]; while (r[i + k] == r[j + k]) k++; height[rank[i]] = k; } } int getid(int x) { return idx[sa[x]]; } int solve(int t, int n) { int sum = 0; FE(i, 1, t) { dp[i] = val[i]; sumlen[i] = sum; sum += len[i] + 1; } int nowi; FED(i, t, 1) { nowi = sumlen[i]; int lmin = INF; for (int j = rank[nowi] + 1; j <= n; j++) { lmin = min(lmin, height[j]); if (lmin < len[i]) break; if (nowi < sa[j]) dp[i] = max(dp[i], val[i] + dp[getid(j)]); } lmin = INF; for (int j = rank[nowi] - 1; j > 0; j--) { lmin = min(lmin, height[j + 1]); if (lmin < len[i]) break; if (nowi < sa[j]) dp[i] = max(dp[i], val[i] + dp[getid(j)]); } } int ans = 0; FE(i, 1, t) ans = max(ans, dp[i]); return ans; } int main() { int test; int t, n, m; int ncase = 1; RI(test); while (test--) { n = 0; m = 256; CLR(idx, 0); RI(t); FE(i, 1, t) { RS(r); RI(val[i]); int l = len[i] = strlen(r); REP(j, l) { a[n] = (int)r[j]; idx[n++] = i; } a[n++] = m++; } a[--n] = 0; --m; build_sa(a, sa, n + 1, m); getHeight(a, sa, n); printf(Case #%d: %d , ncase++, solve(t, n)); } return 0; }

hdu 4117 GRE Words （ac自动机 线段树 dp）