上一篇:
字符串算法复习(一)
下一篇:
字符串算法复习(三)
BZOJ 2434
题目大意:
有一个打字机支持三种操作:
1.在字符串末尾加入一个小写字符。
2.删去字符串末尾的字符。
3.输出当前字符串, 注意这样并不会清空字符串。
阿狸用这个打字机进行了一波操作之后给了M个询问, 对于每次询问(x, y)回答第x个打印的字符串在第y个打印的字符串中出现了多少次。
解题报告
比较好的题目!
首先可以用这个操作序列建立AC自动机, 因为这个操作序列的长度严格大于Trie树遍历序的长度所以不会爆内存。
然后建立fail树, 发现每次询问(x, y)相当于问y串上的全部节点中有多少在代表x的节点的子树内。
按照fail树代表字符串y的节点的dfn序离线所有询问(直接用输入顺序离线也可以, 只是会稍微慢一点, 代码中是按照输入顺序离线的), 用树状数组+dfn序维护子树和, 用一个栈保存当前Trie树上y的路径, 每次y变化时暴力修改即可, 每个节点只会被插入/删除一次。
第一次一波AC…感动…
我果然还是太菜了
代码
#include <cstdio> #include <cstring> #include <algorithm> #include <cstdlib> #include <climits> #include <queue> #include <map> using namespace std; typedef unsigned long long ULL; const int MAXL = 100010; namespace Qtree { const int MAXD = MAXL; struct Node { int v, nxt; } d[MAXD]; int head[MAXD], etot; inline void addEdge (int a, int b) { etot ++; d[etot].v = b; d[etot].nxt = head[a]; head[a] = etot; } int dfn[MAXD], dfnlst[MAXD], dfntot; void dfs (int u) { dfn[u] = ++dfntot; for(int e = head[u]; e; e = d[e].nxt) dfs(d[e].v); dfnlst[u] = dfntot; } int C[MAXL]; inline int lowbit (int a) {return a&-a;} inline void add (int p, int v) { while(p <= dfntot) { C[p] += v; p += lowbit(p); } } inline int qry (int p) { int ret = 0; while(p) { ret += C[p]; p -= lowbit(p); } return ret; } void modify (int u, int v) { add(dfn[u], v); } int query (int u) { return qry(dfnlst[u])-qry(dfn[u]-1); } } namespace Trie { const int MAXD = MAXL; struct Node { int ch[26]; int pre; } d[MAXD]; int dtot, stot; int strends[MAXL]; int stk[MAXL], stktop; inline void pchar (char ch) { if(ch == 'P') strends[++stot] = stk[stktop]; else if(ch == 'B') stktop --; else { if(d[stk[stktop]].ch[ch-'a'] == 0) d[stk[stktop]].ch[ch-'a'] = ++dtot; stk[stktop+1] = d[stk[stktop]].ch[ch-'a']; ++ stktop; } } inline void build (char *str) { while(*str != '\0') { pchar(*str); ++ str; } } queue<int> que; void setup () { que.push(0); while(!que.empty()) { int u = que.front(); que.pop(); for(int ch = 0; ch < 26; ch++) { if(d[u].ch[ch] != 0) { int v = d[u].ch[ch]; if(d[u].pre != u) d[v].pre = d[d[u].pre].ch[ch]; Qtree :: addEdge(d[v].pre, v); que.push(v); } else d[u].ch[ch] = d[d[u].pre].ch[ch]; } } } int qtot = 0; pair<int, int> qry[MAXL]; int ans[MAXL], qy[MAXL]; void feedQuery (int a, int b) { qry[++qtot] = make_pair(a, b); } inline bool comp (int a, int b) { return qry[a].second < qry[b].second; } int ctot; inline int wchar (char ch) { if(ch == 'P') ++ctot; else if(ch == 'B') Qtree :: modify(stk[stktop], -1), stktop --; else { stk[stktop+1] = d[stk[stktop]].ch[ch-'a']; Qtree :: modify(stk[++ stktop], 1); } return stk[stktop]; } void solve (char * str) { Qtree :: dfs(0); for(int i = 1; i<=qtot; i++) qy[i] = i; std :: sort(qy+1, qy+qtot+1, comp); stktop = 0; for(int q = 1; q<=qtot; q++) { int qid = qy[q]; while(ctot < qry[qid].second) wchar(*str), ++ str; ans[qid] = Qtree :: query(strends[qry[qid].first]); } } } char str[MAXL]; int main () { scanf("%s", str); Trie :: build(str); Trie :: setup(); int M, a, b; scanf("%d", &M); for(int i = 1; i<=M; i++) { scanf("%d%d", &a, &b); Trie :: feedQuery(a, b); } Trie :: solve(str); for(int i = 1; i<=M; i++) printf("%d\n", Trie :: ans[i]); }
BZOJ 1212
题目大意: 给你N个模式串, Q次询问, 每次询问一个串是否能够由着N个模式串链接而成, 每个串可以使用多次。
N小于等于20
解题报告
大暴力…N只有20, 把终止标记沿着fail链直接下传即可…
代码
#include <cstdio> #include <cstring> #include <algorithm> #include <climits> #include <cstdlib> #include <vector> #include <queue> using namespace std; const int MAXL = 1300000; namespace Trie { const int MAXD = MAXL; struct Node { int ch[26]; int pre; vector<int> mark; } d[MAXD]; int dtot; inline void insert (char * str) { int dep = 0, u = 0; while(*str != '\0') { ++ dep; if(d[u].ch[*str-'a'] == 0) d[u].ch[*str-'a'] = ++dtot; u = d[u].ch[*str-'a']; ++ str; } d[u].mark.push_back(dep); } queue<int> que; void setup () { que.push(0); while(!que.empty()) { int u = que.front(); que.pop(); for(int ch = 0; ch<26; ch++) if(d[u].ch[ch] != 0) { int v = d[u].ch[ch]; if(d[u].pre != u) d[v].pre = d[d[u].pre].ch[ch]; d[v].mark.insert(d[v].mark.end(), d[d[v].pre].mark.begin(), d[d[v].pre].mark.end()); que.push(v); } else d[u].ch[ch] = d[d[u].pre].ch[ch]; } } bool dp[MAXL]; int query (char * str) { int u = 0, ans = 0, clen = 0; memset(dp, 0, sizeof dp); dp[0] = true; while(*str != '\0') { ++ clen; u = d[u].ch[*str - 'a']; for(int i = 0; i<(int)d[u].mark.size(); i++) dp[clen] |= dp[clen-d[u].mark[i]]; if(dp[clen]) ans = clen; //printf("dp[%d]:%d\n", clen, dp[clen]); ++ str; } return ans; } } char buf[MAXL]; int main () { int N, M; scanf("%d%d", &N, &M); for(int i = 1; i<=N; i++) { scanf("%s", buf); Trie :: insert(buf); } Trie :: setup(); for(int i = 1; i<=M; i++) { scanf("%s", buf); printf("%d\n", Trie :: query(buf)); } }
BZOJ 4278
题目大意: 有两个队列装了一些字符, 每次你可以取出一个队首塞到字符串s的结尾, 问把两个队列取空后最小的s。
解题报告
首先这题不AC自动机了..
发现如果把队尾元素设成INF后, 可以贪心地一直取字典序较小的队列队首来构造。
这就涉及到快速比较两个字符串任意后缀之间的大小了…当然可以上后缀数组, 但是我懒嘛…
于是使用了来自哈希的神秘力量——二分lcp…
代码
#include <cstdio> #include <cstring> #include <algorithm> #include <climits> #include <cstdlib> #include <vector> #include <queue> using namespace std; typedef unsigned long long ULL; const int MAXL = 200020; const ULL SEED = 1091; int A, B; int q1[MAXL], q2[MAXL]; ULL hashc1[MAXL], hashc2[MAXL], powr[MAXL]; int getLCP (int a, int b) { int l = 0, r = max(A-a, B-b); int ans = -1; while(l <= r) { int mid = (l+r)>>1; if(hashc1[a+mid]-hashc1[a-1]*powr[mid+1] == hashc2[b+mid]-hashc2[b-1]*powr[mid+1]) l = mid+1, ans = mid; else r = mid-1; } return ans; } int main () { scanf("%d", &A); for(int i = 1; i<=A; i++) scanf("%d", &q1[i]); for(int i = 1; i<=A; i++) hashc1[i] = hashc1[i-1]*SEED+q1[i]; scanf("%d", &B); for(int i = 1; i<=B; i++) scanf("%d", &q2[i]); for(int i = 1; i<=B; i++) hashc2[i] = hashc2[i-1]*SEED+q2[i]; powr[0] = 1; int mx = max(A, B); for(int i = 1; i<=mx; i++) powr[i] = powr[i-1]*SEED; q1[A+1] = 9999, q2[B+1] = 9999; int l = 1, r = 1; while(l <= A || r <= B) { if(l <= A && r <= B) { int lcp = getLCP(l, r); if(q1[l+lcp+1] < q2[r+lcp+1]) printf("%d ", q1[l++]); else printf("%d ", q2[r++]); } else if(l > A) printf("%d ", q2[r++]); else printf("%d ", q1[l++]); } }
后缀数组专题开始
前言
貌似后缀数组可以用哈希求?Nlog^2?
int N; ULL hashc[MAXN], powr[MAXN]; int A[MAXN], yy[MAXN]; inline int getLCP (int a, int b) { int l = 1, r = min(N-a, N-b), ret = 0; while(l <= r) { int mid = (l+r)>>1; if(hashc[a+mid-1]-hashc[a-1]*powr[mid+1] == hashc[b+mid-1]-hashc[b-1]*powr[mid+1]) l = mid+1, ret = mid; else r = mid-1; } return ret; } bool comp (int a, int b) { int lcp = getLCP(a, b); return delta[a+lcp] < delta[b+lcp]; } std :: sort(yy+1, yy+N+1, comp);
算了还是不要搞这种鬼畜玩意儿了…
发现已经忘记一切…重新学习
模板
一坨细节, 贴个模板
int mem[2][MAXL], buk[MAXL]; void suffixArray (int * A, int * sa, int len, int chr, int *x, int *y) { memset(buk, 0, sizeof buk); for(int i = 0; i<len; i++) ++ buk[A[i]]; for(int i = 1; i<chr; i++) buk[i] += buk[i-1]; for(int i = len-1; i>=0; i--) sa[--buk[x[i] = A[i]]] = i; for(int cur = 1, p = 0; p < len-1; cur<<=1, chr = p+1) { p = 0; for(int i = len-cur; i<len; i++) y[p++] = i; for(int i = 0; i<len; i++) if(sa[i] >= cur) y[p++] = sa[i]-cur; memset(buk, 0, sizeof buk); for(int i = 0; i<len; i++) buk[x[y[i]]] ++; for(int i = 1; i<chr; i++) buk[i] += buk[i-1]; for(int i = len-1; i>=0; i--) sa[-- buk[x[y[i]]]] = y[i]; swap(x, y); x[sa[0]] = 0; p = 0; for(int i = 1; i<len; i++) x[sa[i]] = (y[sa[i]] == y[sa[i-1]] && y[sa[i]+cur] == y[sa[i-1]+cur]) ? p : ++p; //printf("p:%d, cur:%d\n", p, cur); } } void suffixHeight (int * A, int len, int chr, int * sa, int * rk, int * he) { A[len] = 0; // 极小值 suffixArray(A, sa, len+1, chr, mem[0], mem[1]); for(int i = 1; i<=len; i++) rk[sa[i]+1] = i; int k = 0; for(int i = 1; i<=len; i++) { for(k?k--:k; A[sa[rk[i]-1]+k] == A[sa[rk[i]]+k]; ++k) ; he[rk[i]] = k; } }
BZOJ 2119
题目大意:自己看..
统计+后缀数组, 这题真的很强, 很神…但是我懒得写题解了…直接贴代码吧。
有时间我再补。
代码
#include <cstdio> #include <cstring> #include <algorithm> #include <climits> #include <cstdlib> using namespace std; typedef long long LL; const int MAXL = 50050; int qlogtb[MAXL]; void qlogProp () { int t = 0; for(int i = 2; i<MAXL; i<<=1) qlogtb[i] = ++t; for(int i = 1; i<MAXL; i++) qlogtb[i] = max(qlogtb[i-1], qlogtb[i]); } struct SuffixArray { int mem[2][MAXL], buk[MAXL]; void suffixArray (int * A, int * sa, int len, int chr, int *x, int *y) { memset(buk, 0, sizeof buk); for(int i = 0; i<len; i++) ++ buk[A[i]]; for(int i = 1; i<chr; i++) buk[i] += buk[i-1]; for(int i = len-1; i>=0; i--) sa[--buk[x[i] = A[i]]] = i; for(int cur = 1, p = 0; p < len-1; cur<<=1, chr = p+1) { p = 0; for(int i = len-cur; i<len; i++) y[p++] = i; for(int i = 0; i<len; i++) if(sa[i] >= cur) y[p++] = sa[i]-cur; memset(buk, 0, sizeof buk); for(int i = 0; i<len; i++) buk[x[y[i]]] ++; for(int i = 1; i<chr; i++) buk[i] += buk[i-1]; for(int i = len-1; i>=0; i--) sa[-- buk[x[y[i]]]] = y[i]; swap(x, y); x[sa[0]] = 0; p = 0; for(int i = 1; i<len; i++) x[sa[i]] = (y[sa[i]] == y[sa[i-1]] && y[sa[i]+cur] == y[sa[i-1]+cur]) ? p : ++p; //printf("p:%d, cur:%d\n", p, cur); } } void suffixHeight (int * A, int len, int chr, int * sa, int * rk, int * he) { A[len] = 0; // 极小值 suffixArray(A, sa, len+1, chr, mem[0], mem[1]); for(int i = 1; i<=len; i++) rk[sa[i]] = i; int k = 0; for(int i = 0; i<len; i++) { for(k?k--:k; A[sa[rk[i]-1]+k] == A[sa[rk[i]]+k]; ++k) ; he[rk[i]] = k; } } int sa[MAXL], rk[MAXL], he[MAXL]; int minv[MAXL][20]; void build (int * src, int len, int chr) { chr += 10; suffixHeight(src, len, chr, sa, rk, he); for(int i = 1; i<=len; i++) minv[i][0] = he[i]; for(int lvl = 1; (1<<lvl) <= len; lvl++) for(int i = 1; i<=len; i++) { if(i+(1<<(lvl-1)) <= len) minv[i][lvl] = min(minv[i][lvl-1], minv[i+(1<<(lvl-1))][lvl-1]); else minv[i][lvl] = minv[i][lvl-1]; } } int query (int a, int b) { if(a == b) throw "wtf"; a = rk[a], b = rk[b]; if(a > b) swap(a, b); a ++; int lval = qlogtb[b-a+1]; return min(minv[a][lval], minv[b-(1<<lval)+1][lval]); } } pfix, sfix; int A[MAXL], src[MAXL], yy[MAXL]; LL delta[MAXL]; inline bool compY (int a, int b) {return delta[a] < delta[b];} int main () { qlogProp(); int N, M; scanf("%d%d", &N, &M); for(int i = 1; i<=N; i++) scanf("%d", &A[i]); for(int i = 2; i<=N; i++) delta[i] = (LL)A[i]-A[i-1], yy[i] = i; std :: sort(yy+2, yy+N+1, compY); int itot = 1; src[yy[2]-2] = itot; for(int i = 3; i<=N; i++) src[yy[i]-2] = (delta[yy[i]] == delta[yy[i-1]]) ? itot : ++itot; sfix.build(src, N-1, itot+1); reverse(src, src+N-1); pfix.build(src, N-1, itot+1); reverse(src, src+N-1); int ans = 0; for(int clen = 1; clen*2+M < N; clen++) { //printf("clen:%d\n", clen); for(int i = 0; i<N-1; i+=clen) { int j = i+clen+M; if(j >= N-1) break; int lcp = pfix.query(N-i-2, N-j-2); int lcs = sfix.query(i, j); //printf("p:%d, %d, lcplcs:%d, %d\n", i, j, lcp, lcs); lcp = min(lcp, clen), lcs = min(lcs, clen); if(lcp || lcs) { if(lcp+lcs-1 >= clen) ans += lcp+lcs-clen; } } } printf("%d\n", ans); }
BZOJ 1692
题目大意:给你一个大写字母串和一个空串s, 问每次从串首或串尾取出一个字符加入到字符串s的末尾, 取空串后能形成的字典序最小的s。
解题报告
显然按照取字典序较小的位置更好, 转化成BZOJ4278。
这次写了一波后缀数组, 没有用哈希了。
代码
#include <cstdio> #include <cstring> #include <algorithm> #include <climits> #include <cstdlib> using namespace std; typedef long long LL; const int MAXL = 30030; char buf[10]; int src[MAXL*2]; int mem[2][MAXL*2], buk[MAXL*2]; void suffixArray (int * A, int len, int chr, int * sa) { int * x = mem[0], * y = mem[1]; memset(buk, 0, sizeof buk); for(int i = 0; i<len; i++) ++ buk[x[i] = A[i]]; for(int i = 1; i<chr; i++) buk[i] += buk[i-1]; for(int i = len-1; i>=0; i--) sa[--buk[x[i]]] = i; for(int cur = 1, p = 0; p+1<len; chr = p+1, cur<<=1) { p = 0; for(int i = len-cur; i<len; i++) y[p++] = i; for(int i = 0; i<len; i++) if(sa[i] >= cur) y[p++] = sa[i]-cur; memset(buk, 0, sizeof buk); for(int i = 0; i<len; i++) ++ buk[x[i]]; for(int i = 1; i<chr; i++) buk[i] += buk[i-1]; for(int i = len-1; i>=0; i--) sa[-- buk[x[y[i]]]] = y[i]; swap(x, y); x[sa[0]] = 0; p = 0; for(int i = 1; i<len; i++) x[sa[i]] = (y[sa[i]] == y[sa[i-1]] && y[sa[i]+cur] == y[sa[i-1]+cur]) ? p : ++p; } } int sa[MAXL*2], rk[MAXL*2]; int main () { int N; scanf("%d", &N); for(int i = 1; i<=N; i++) { scanf("%s", buf); src[i-1] = buf[0]-'A'+1; } for(int i = N+1; i<=(N<<1); i++) src[i] = src[N-(i-N)]; int len = (N<<1)+1; src[len] = 0; suffixArray(src, len+1, 27, sa); for(int i = 1; i<=len; i++) rk[sa[i]] = i; int l = 0, r = N-1; int cnt = 0; while(l < r) { int r1 = rk[l], r2 = rk[N*2-r]; if(r1 < r2) putchar(src[l++]+'A'-1); else putchar(src[r--]+'A'-1); cnt ++; if(cnt == 80) cnt = 0, putchar('\n'); } putchar(src[l]+'A'-1); }
BZOJ 1031
题目大意: 给出字符串s, 首尾连接形成一个环。对于每一个环上的字符i取出这个字符开始向后len个字符形成字符串sub i , 把所有sub串排序后依次输出每个sub串末尾的字符。
解题报告
用后缀数组模拟即可。
代码
#include <cstdio> #include <cstring> #include <algorithm> #include <climits> #include <cstdlib> using namespace std; typedef long long LL; const int MAXL = 100020; int buk[MAXL*2], mem[2][MAXL*2]; void suffixArray (int * A, int len, int chr, int * sa) { int *x = mem[0], *y = mem[1]; memset(buk, 0, sizeof buk); for(int i = 0; i<len; i++) ++ buk[x[i] = A[i]]; for(int i = 1; i<chr; i++) buk[i] += buk[i-1]; for(int i = len-1; i>=0; i--) sa[-- buk[x[i]]] = i; for(int cur = 1, p = 0; p+1<len; chr = p+1, cur<<=1) { p = 0; for(int i = len-cur; i<len; i++) y[p++] = i; for(int i = 0; i<len; i++) if(sa[i] >= cur) y[p++] = sa[i]-cur; memset(buk, 0, sizeof buk); for(int i = 0; i<len; i++) ++ buk[x[i]]; for(int i = 1; i<chr; i++) buk[i] += buk[i-1]; for(int i = len-1; i>=0; i--) sa[-- buk[x[y[i]]]] = y[i]; swap(x, y); x[sa[0]] = 0; p = 0; for(int i = 1; i<len; i++) x[sa[i]] = (y[sa[i]] == y[sa[i-1]] && y[sa[i]+cur] == y[sa[i-1]+cur]) ? p : ++p; } } char str[MAXL]; int src[MAXL*2], sa[MAXL*2]; int main () { scanf("%s", str); int len = strlen(str); for(int i = 0; i<len; i++) src[i] = src[len+i] = str[i]; suffixArray(src, len*2+1, 128, sa); int cnt = 0; for(int i = 1; cnt<len; i++) { if(sa[i] < len) { cnt++; putchar(src[sa[i]+len-1]); } } }
JeremyGuo
你的主题好难看
Pingback: 简单字符串算法复习(三) « Hineven!
Pingback: 字符串算法复习(三) « Hineven!
Pingback: 字符串算法复习(一) « Hineven!