首页 > 代码库 > 字符串·Part 1
字符串·Part 1
字符串算法有哪些呢？？？Tire,KM,KMP,AC自动机,后缀数组,后缀自动机,RK,Shift-And/Or,Manacher.....
™这么这么多啊！！！
也只能慢慢学了。。。
接下来的题是按我做题顺序来排的，难度的话我就不理了(`?ω?´)
BZOJ 2434: [NOI2011]阿狸的打字机
第一道字符串就做这道简直大丈夫！
先建棵ACTree和FailTree，保存每个字符串的末节点位置。
然后从树根一步一步走，根至当前节点的字符串就是当前打字机内的字符串，一边走一边离线查询。
对于每个查询(x,y)在查到s[y]的末尾节点的时候开始计算，用DFS序思想和树状数组求s[x]的末尾节点的Fail子树中包含了几个s[y]的节点，这就是答案了。
当时AC自动机不会，FailTree不会，后缀数组不会，DFS序没想到。。。QAQ
1 #include <algorithm> 2 #include <cstdio> 3 #include <iostream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <vector> 7 #include <queue> 8 9 #define rep(i, l, r) for(int i = l; i <= r; i++)10 #define down(i, l, r) for(int i = l; i >= r; i--)11 #define MS 12345612 #define MAX 103747182313 14 using namespace std;15 16 struct node 17 { 18 int x, y, n; 19 bool operator < (const node &k) const { return x < k.x; };20 } e[MS]; int ec, fir[MS];21 int c[MS], r[MS][26], f[MS], h[MS], tc, ss[MS], ds[MS], dt[MS], k[MS];22 queue<int> p;23 int n, m, x, y, now, nq;24 char s[MS];25 26 void DFS(int x)27 {28 int o = fir[x]; ds[x] = ++now;29 while (o) { DFS(e[o].y); o = e[o].n; }30 dt[x] = now;31 }32 33 inline void Add(int x, int z)34 { int o = x; while (o<=tc+1) k[o]+=z, o = o+(o&(-o)); }35 36 inline int Qsum(int x)37 {38 int o = x, ans=0; while (o) ans+=k[o], o = o-(o&(-o)); 39 return ans;40 }41 42 inline void Query(int x)43 {44 while (e[nq].x == x)45 { int y=e[nq].y; e[nq].y = Qsum(dt[ss[y]]) - Qsum(ds[ss[y]]-1); nq++; }46 }47 48 int main()49 {50 scanf("%s", s); int l=strlen(s); f[0] = -1;51 rep(i, 0, l-1) 52 if (s[i]!=‘P‘ && s[i]!=‘B‘) 53 { if (!r[now][s[i]-‘a‘]) tc++, r[now][s[i]-‘a‘]=tc, h[tc]=now, c[tc]=s[i]-‘a‘; now=r[now][s[i]-‘a‘]; }54 else if (s[i]==‘P‘) ss[++n] = now; 55 else now = h[now];56 rep(i, 0, tc) f[i] = -1; p.push(0);57 while (!p.empty())58 {59 x = p.front(); p.pop();60 rep(i, 0, 25) if (r[x][i])61 {62 int fo = f[x]; 63 while (fo >= 0)64 { if (r[fo][i]) break; else fo = f[fo]; }65 if (fo < 0) f[r[x][i]] = 0; else f[r[x][i]] = r[fo][i];66 p.push(r[x][i]);67 }68 }69 down(i, tc, 1) e[i].y = i, e[i].n = fir[f[i]], fir[f[i]] = i; now = 0; DFS(0);70 rep(i, 1, tc) fir[i] = 0;71 scanf("%d", &m);72 rep(i, 1, m)73 { scanf("%d%d", &x, &y); e[i].x = y, e[i].y = x, e[i].n = i; }74 sort(e+1, e+1+m);75 now=n=0; nq=1; rep(i, 0, l-1) 76 if (s[i]!=‘P‘ && s[i]!=‘B‘) { now=r[now][s[i]-‘a‘]; Add(ds[now], 1); }77 else if (s[i]==‘P‘) Query(++n); else { Add(ds[now], -1); now = h[now]; }78 rep(i, 1, m) e[i].x = e[i].n; sort(e+1, e+1+m); rep(i, 1, m) printf("%d\n", e[i].y);79 return 0;80 }
字符串·Part 1
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。