最终得对抗自己

字符串算法复习(二)

Hineven - November 20, 2017 - 4 comments

上一篇: 字符串算法复习(一)
下一篇: 字符串算法复习(三)

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]);
        }
    }
}

Categories : OI生涯 , OI解题报告 , 字符串
Tags : ,

评论列表

  1. JeremyGuo Reply

    你的主题好难看

  2. Pingback: 简单字符串算法复习(三) « Hineven!

  3. Pingback: 字符串算法复习(三) « Hineven!

  4. Pingback: 字符串算法复习(一) « Hineven!

Leave a Reply to JeremyGuo Cancel reply

Your email address will not be published. Required fields are marked *

！

  • Elaine，月亮姐姐
  • Ender，社会主义魔王
  • Farmer，农民
  • Hineven，社会主义常数
  • JeremyGuo，社会主义太师
  • Miracle没有留太多梗
  • SinGuLarity，文青
  • SunIsMe，社会主义教皇
  • XJC，老实的死宅
  • YUKI，记忆力小王子
AFO