后缀自动机合集 II

发布时间:2016-12-11 21:59:18 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"后缀自动机合集 II",主要涉及到后缀自动机合集 II方面的内容,对于后缀自动机合集 II感兴趣的同学可以参考一下。

补充 在SAM中,state_Ai->nxt[w] == stateB ( w: const ) stateB->fa->step <= state_Ai->step ( state_Ai->nxt[w] == stateB ) 利用拓扑排序,可构建所有子串在原串中出现的次数 hdu 3518 Boring counting SAM中的每个状态点都表示为从root出发走到该点所构成的子串,若其作为其他状态的父节点,则说明该子串被其他子串共享。 求出现两次以上且不重复的子串数量只要对每个点记录最早最晚出现的位置 两位置间距大于所表示的串长,res += p->step - p->fa->step 否则,取其中的部分 #include <stdio.h> #include <vector> #include <string.h> #include <algorithm> using namespace std; const int MAXN = 1010; char s[MAXN ]; struct node { node*nxt[26], *fa; int step; int pos; int fst, lst; int num; void clear() { fa = 0, step = 0; fst = lst = 0; num = 0; memset ( nxt, 0, sizeof nxt ); } } *root, *tail, nodePool[MAXN << 1], *cur, *cnt; void init() { cur = nodePool; root = tail = cur++; root->clear(); root->pos = 0; } void Insert ( int w ) { node *p = tail, *np = cur++; np->clear(); np->step = p->step + 1; np->pos = np->step; for ( ; p && !p->nxt[w]; p = p->fa ) { p->nxt[w] = np; } if ( !p ) { np->fa = root; } else { if ( p->nxt[w]->step == p->step + 1 ) { np->fa = p->nxt[w]; } else { node *q = p->nxt[w], *r = cur++; *r = *q; r->step = p->step + 1; q->fa = np->fa = r; for ( ; p && p->nxt[w] == q; p = p->fa ) { p->nxt[w] = r; } } } tail = np; } int c[MAXN]; node *seq[MAXN << 1]; void solve() { node *a = nodePool; node *p; for ( char *p = s; *p; ++p ) { int w = *p - 'a'; a = a->nxt[w]; a->fst = a->lst = a->pos; a->num = 1; } memset ( c, 0, sizeof c ); for ( int i = 0; i < cur - nodePool; ++i ) { c[nodePool[i].pos]++; } for ( int i = 1; i <= tail->pos; ++i ) { c[i] += c[i - 1]; } for ( int i = 0; i < cur - nodePool; ++i ) { seq[--c[nodePool[i].pos]] = nodePool + i; } for ( int i = cur - nodePool - 1; i >= 0; --i ) { p = seq[i]; if ( p->fst == 0 && p->lst == 0 ) { p->fst = p->lst = p->pos; } if ( p->fa ) { node *q = p->fa; q->num += p->num; if ( q->fst == 0 || q->fst > p->fst ) { q->fst = p->fst; } if ( q->lst == 0 || q->lst < p->lst ) { q->lst = p->lst; } } } int res = 0; for ( p= root+1; p< cur; ++p) { if (p->num > 1) { if ( p->lst - p->fst >= p->step) res += p->step - p->fa->step; else if (p->lst - p->fst > p->fa->step) res += p->lst - p->fst - p->fa->step; } } printf("%d\n", res); } int main() { #ifdef __GNUC__ freopen ( "in.txt", "r", stdin ); #endif // __GNUC__ while ( scanf ( "%s", s ) != EOF && s[0] != '#' ) { init(); for ( char *p = s; *p; ++p ) { Insert ( *p - 'a'); } solve(); } return 0; } CF 235C. Cyclical Quest 菜鸟从未碰过CF,通过大神们的博客找到这题 开始还一直卡在如何确定当前已匹配长度串在SAM中的位置,果然理解还是不够 #include <stdio.h> #include <iostream> #include <vector> #include <string.h> #include <algorithm> using namespace std; const int MAXN = 1000010; typedef long long LL; char s[MAXN << 1]; struct node { node*nxt[26], *fa; int step; int flg; int num; void clear() { fa = 0, step = 0; flg = -1; num = 0; memset ( nxt, 0, sizeof nxt ); } } *root, *tail, nodePool[MAXN << 1], *cur; void init() { cur = nodePool; root = tail = cur++; root->clear(); } void Insert ( int w ) { node *p = tail, *np = cur++; np->clear(); np->step = p->step + 1; for ( ; p && !p->nxt[w]; p = p->fa ) { p->nxt[w] = np; } if ( !p ) { np->fa = root; } else { if ( p->nxt[w]->step == p->step + 1 ) { np->fa = p->nxt[w]; } else { node *q = p->nxt[w], *r = cur++; *r = *q; r->step = p->step + 1; q->fa = np->fa = r; for ( ; p && p->nxt[w] == q; p = p->fa ) { p->nxt[w] = r; } } } tail = np; } int c[MAXN]; node *seq[MAXN << 1]; void preInit() { node *a; memset ( c, 0, sizeof c ); for ( int i = 0; i < cur - nodePool; ++i ) { c[nodePool[i].step]++; } for ( int i = 1; i <= tail->step; ++i ) { c[i] += c[i - 1]; } for ( int i = 0; i < cur - nodePool; ++i ) { seq[--c[nodePool[i].step]] = nodePool + i; } a = root; for ( char *st = s; *st; ++st ) { a = a->nxt[*st - 'a']; a->num = 1; } for ( int i = cur - nodePool - 1; i >= 0; --i ) { a = seq[i]; if ( a->fa ) { a->fa->num += a->num; } } } void solve ( int cao ) { int len = strlen ( s ), w, l; LL res = 0; node *p = root; int sum = 0; memcpy ( s + len, s, ( len - 1 ) ); l = len; len = len * 2 - 1; * ( s + len ) = 0; for ( int i = 0; i < len; ++i ) { w = s[i] - 'a'; if ( p->nxt[w] ) { sum++, p = p->nxt[w]; } else { while ( p && p->nxt[w] == NULL ) { p = p->fa; } if ( !p ) { sum = 0, p = root; } else { sum = p->step + 1, p = p->nxt[w]; } } if ( i >= l - 1 && sum >= l ) { node *q = p; while ( 1 ) { if ( l > q->fa->step && p->step >= l ) { break; } q = q->fa; } if ( q->flg != cao ) { res += q->num; q->flg = cao; } } } cout << res << endl; } int main() { #ifdef __GNUC__ freopen ( "in.txt", "r", stdin ); #endif // __GNUC__ int n; scanf ( "%s", s ); init(); for ( char *p = s; *p; ++p ) { Insert ( *p - 'a' ); } preInit(); scanf ( "%d", &n ); for ( int i = 1; i <= n; ++i ) { scanf ( "%s", s ); solve ( i ); } return 0; } hdu 4641 K-string 主要考对SAM基础的理解,还有些烦到死的优化 #include <stdio.h> #include <iostream> #include <vector> #include <string.h> #include <algorithm> using namespace std; const int MAXN = 260000; typedef long long LL; char s[MAXN]; int n, m, k; int res; struct node { node*nxt[26], *fa; int step; int num; int flag; void clear() { fa = 0, step = 0; num = 0; flag = 0; memset ( nxt, 0, sizeof nxt ); } } *root, *tail, nodePool[MAXN << 1], *cur; void init() { cur = nodePool; root = tail = cur++; root->clear(); res = 0; } void Insert ( int w ) { node *p = tail, *np = cur++; np->clear(); np->step = p->step + 1; for ( ; p && !p->nxt[w]; p = p->fa ) { p->nxt[w] = np; } if ( !p ) { np->fa = root; np->num ++; if ( 1 >= k ) { res += np->step; np->flag = 1;} } else { if ( p->nxt[w]->step == p->step + 1 ) { node *q = np; np->fa = p->nxt[w]; while ( q != root && !q->flag ) { q->num++; if ( q->num >= k ) { res += q->step - q->fa->step; q->flag = 1; } q = q->fa; } } else { node *q = p->nxt[w], *r = cur++; node *wocao = q->fa; *r = *q; r->step = p->step + 1; np->num++; r->num = 1 + q->num; if ( r->num >= k ) { res += r->step - wocao->step; r->flag = 1;} for ( node *as = q->fa; as != root && !as->flag; as = as->fa ) { as->num++; if ( as->num >= k ) { res += as->step - as->fa->step; as->flag = 1; } } if ( q->num >= k ) { res -= q->step - wocao->step; } q->fa = np->fa = r; if ( q->num >= k ) { res += q->step - r->step; } if ( np->num >= k ) { res += np->step - r->step; np->flag = 1;} for ( ; p && p->nxt[w] == q; p = p->fa ) { p->nxt[w] = r; } } } tail = np; } int main() { #ifdef __GNUC__ freopen ( "in.txt", "r", stdin ); #endif // __GNUC__ while ( scanf ( "%d%d%d", &n, &m, &k ) == 3 ) { scanf ( "%s", s ); init(); for ( char *p = s; *p; ++p ) { Insert ( *p - 'a' ); } int a; while ( m-- ) { scanf ( "%d", &a ); if ( a == 1 ) { scanf ( "%s", s ); Insert ( s[0] - 'a' ); } else { printf ( "%d\n", res ); } } } return 0; }

上一篇:说说gui程序的开发中所谓的“主线程”概念
下一篇:编译原理序列

相关文章

相关评论