最终得对抗自己

字符串算法复习(一)

Hineven - November 17, 2017 - 2 comments

貌似有点长, 分多篇博客写。
下一篇 字符串算法复习(二)

除了cf那道题应该都是老套路了…神犇说刷一遍

Codeforces 30E

题目大意:给你一个串S, 求删去S的一个前缀和子串s1和s2(不能删后缀)之后剩下的三个串ABC的最大长度和。
其中, length(A) == length(C), length(B)%2 == 1 并且ABC是一个回文串。

解题报告

大乱搞!
SunIsMe:我有[latex]N\times log_{2}^{2}(N)[/latex]的算法!
Hineven:我有[latex]N\times log_{\frac{3}{2}}(N)[/latex]的算法!
JeremyGuo:我有[latex]N\times log_{2}(N)[/latex]的算法!
Ender:我有线性算法!
说下我的做法吧…
首先发现C的长度和答案构成的函数是单峰的, 三分C的长度, 用哈希从头开始匹配第一个A, 然后用manacher做回文串找出B。

代码 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cmath>
using namespace std;
typedef unsigned long long ULL;
const int MAXL = 100010;
const ULL SEED = 31;
int len;
char str[MAXL];
int plen[MAXL], mxv[MAXL];
void manacher (char * s, int clen) {
    int mxp = 1;
    plen[1] = 0;
    for(int i = 1; i<=clen; i++) {
        if(mxp+plen[mxp] > i) plen[i] = min(plen[mxp-(i-mxp)], mxp+plen[mxp]-i);
        else plen[i] = 0;
        while(i-plen[i] > 0 && i+plen[i] <= clen && s[i-plen[i]] == s[i+plen[i]]) plen[i]++;
        plen[i] --;
        if(i+plen[i] > mxp+plen[mxp]) mxp = i;
    }
    memset(mxv, 0, sizeof mxv);
    for(int i = clen; i>=1; i--) {
        mxv[i-plen[i]] = max(mxv[i-plen[i]], plen[i]*2+1);
        mxv[i] = max(mxv[i], mxv[i+1]);
    }
}
ULL hashv[MAXL], powr[MAXL];
inline ULL hcodeInv (int l, int r) {
    return hashv[r]-hashv[l-1]*powr[r-l+1];
}
pair<int, int> check (int suflen) {
    ULL sufcode = 0;
    for(int i = len; i>=len-suflen+1; i--)
        sufcode = sufcode*SEED+str[i];
    manacher(str, len-suflen);
    for(int i = 1; i<=len-(suflen<<1); i++)
        if(hcodeInv(i, i+suflen-1) == sufcode)
            return pair<int, int>(i, suflen*2+mxv[i+suflen]);
    return pair<int, int>(0, -1);
}
int main () {
    scanf("%s", str+1);
    len = strlen(str+1);
    powr[0] = 1;
    for(int i = 1; i<=len; i++)
        hashv[i] = hashv[i-1]*SEED+str[i], powr[i] = powr[i-1]*SEED;
    int l = 0, r = len, alen;
    pair<int, int> ans(0, 0);
    while(l < r) {
        int mlen = r-l;
        int midl = l+mlen/3;
        int midr = r-mlen/3;
        //printf("cur:[%d, %d]\n", l, r);
        pair<int, int> vall = check(midl);
        pair<int, int> valr = check(midr);
        if((vall.second >= valr.second && vall.second != -1) || valr.second == -1) {
            r = midr-1;
            if(vall.second > ans.second) ans = vall, alen = midl;
        } else {
            l = midl+1;
            if(valr.second > ans.second) ans = valr, alen = midr;
        }
    }
    manacher(str, len-alen);
    memset(mxv, 0, sizeof mxv);
    for(int i = ans.first+alen; i<=len-alen; i++)
        mxv[i-plen[i]] = max(mxv[i-plen[i]], plen[i]*2+1);
    int mpos;
    for(int i = ans.first+alen; i<=len-alen; i++)
        if(ans.second-(alen<<1) == mxv[i]) {mpos = i; break;}
    if(alen == 0) {
        printf("1\n%d %d\n", mpos, ans.second);
        return 0;
    }
    if(ans.first+alen == mpos && mpos+(ans.second-(alen<<1)) == len-alen+1) {
        printf("1\n%d %d\n", ans.first, len-ans.first+1);
        return 0;
    }
    printf("3\n%d %d\n%d %d\n%d %d\n", ans.first, alen, mpos, ans.second-(alen<<1), len-alen+1, alen);
    return 0;
}

BZOJ 3942

有一个S串和一个T串，设当前串为U串，从前往后把S串一个字符一个字符往U串末尾加，若U串后缀为T，则去掉这个后缀, 重复执行。

解题报告

用两个stack分别保存当前答案和加入这个答案字符时T串的匹配位置, 跑KMP, 如果T串匹配上了, 那就把栈连续弹T个字符。

代码 

#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <climits>
#include <cstdio>
using namespace std;
const int MAXL = 1000100;
char s1[MAXL], s2[MAXL];
int pre[MAXL];
void getNxt (char * str, int len) {
    int p = 1, q = 0;
    pre[0] = -1;
    while(p < len)
        if(q == -1 || str[q] == str[p])
            pre[++p] = ++q;
        else q = pre[q];
}
int stk[MAXL], top;
char ans[MAXL];
int main () {
    scanf("%s%s", s1, s2);
    int len1 = strlen(s1), len2 = strlen(s2);
    getNxt(s2, len2);
    int cur = 0;
    for(int i = 0; i<len1; i++) {
        while(cur != -1 && s1[i] != s2[cur]) cur = pre[cur];
        cur ++;
        if(cur == len2) { // match
            top -= len2-1;
            cur = stk[top];
        } else stk[++top] = cur, ans[top] = s1[i];
    }
    ans[top+1] = '\0';
    printf("%s\n", ans+1);
}

BZOJ 1100

题目大意:给你一个多边形, 求对称轴数量。
要求算法线性。

解题报告

计算几何? 字符串! 计算几何? 字符串!
首先发现这个多边形是可以哈希的…对于多边形的一个顶点, 用这个顶点相邻的两条边叉积做哈希值, 对于一条边用这条边的长度做哈希值。
那么哈希完后, 一条对称轴就相当于一个长度为奇数的回文串了。
之前哈希了几次都没哈希成功, 这种哈希太强大啦! Manacher, 上!

代码 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <climits>
using namespace std;
typedef unsigned long long ULL;
const int MAXN = 100010;
int crd[MAXN*2][2];
ULL hashc[MAXN*2], buf[MAXN*4];
int clen[MAXN*4];
ULL calc (int p) {
    ULL x1 = crd[p-1][0], y1 = crd[p-1][1];
    ULL x2 = crd[p][0], y2 = crd[p][1];
    ULL x3 = crd[p+1][0], y3 = crd[p+1][1];
    return (x2-x1)*(y3-y2)-(x3-x2)*(y2-y1);
}
inline ULL pw2 (ULL a) {return a*a;}
int main () {
    int T;
    scanf("%d", &T);
    while(T --) {
        int N;
        scanf("%d", &N);
        for(int i = 1; i<=N; i++)
            scanf("%d%d", &crd[i][0], &crd[i][1]);
        memcpy(crd+N+1, crd+1, 8*N);
        crd[0][0] = crd[N][0], crd[0][1] = crd[N][1];
        crd[(N<<1)+1][0] = crd[1][0], crd[(N<<1)+1][1] = crd[1][1];
        for(int i = 1; i<=(N<<1); i++) {
            hashc[(i-1)<<1] = calc(i);
            hashc[((i-1)<<1)+1] = pw2(crd[i+1][0]-crd[i][0])+pw2(crd[i+1][1]-crd[i][1]);
        }
        hashc[N<<2] = hashc[0];
        int up = N<<2, mxp = 0, ans = 0;
        for(int i = 0; i<=up; i++) {
            if(mxp+clen[mxp] > i) clen[i] = min(mxp+clen[mxp]-i, clen[mxp-(i-mxp)]);
            else clen[i] = 1;
            while(i-clen[i] >= 0 && i+clen[i] <= up && hashc[i-clen[i]] == hashc[i+clen[i]]) ++ clen[i];
            -- clen[i];
            if(i+clen[i] > mxp+clen[mxp]) mxp = i;
        }
        for(int i = 1; i<=(N<<1); i++)
            if(clen[i] >= N || clen[i+(N<<1)] >= N) ans ++;
        printf("%d\n", ans/2);
    }
}

BZOJ 2938

题目大意:给你一些病毒特征码(二进制), 问是否有一个无限长的01串让这个01串中不出现任何病毒特征码。

解题报告

好久没写AC自动机了…手生…
在AC自动机上如果能够找到环, 那么存在(沿着环一直跑), 否然不存在。
注意fail边连向一个终止节点的全部节点都要算作终止节点。

代码 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <climits>
#include <queue>
using namespace std;
typedef unsigned long long ULL;
const int MAXN = 30030;
namespace Trie {
    const int MAXD = MAXN;
    struct Node {
        int ch[2];
        int pre;
        bool mk;
    } d[MAXD];
    int dtot = 0;
    inline void insert (char * str) {
        int u = 0;
        while(*str != '\0') {
            if(d[u].ch[*str-'0'] == 0)
                d[u].ch[*str-'0'] = ++dtot;
            u = d[u].ch[*str-'0'];
            ++ str;
        }
        d[u].mk = true;
    }
    queue<int> que;
    void setup () {
        que.push(0);
        while(!que.empty()) {
            int u = que.front();
            que.pop();
            for(int ch = 0; ch<2; ch++)
                if(d[u].ch[ch]) {
                    int v = d[u].ch[ch];
                    if(d[u].pre != u)
                        d[v].pre = d[d[u].pre].ch[ch];
                    if(d[d[v].pre].mk) d[v].mk = true;
                    que.push(v);
                } else d[u].ch[ch] = d[d[u].pre].ch[ch];
        }
    }
    bool gvis[MAXD], cvis[MAXD];
    bool dfs (int u) {
        if(d[u].mk) return false;
        if(gvis[u]) {
            if(cvis[u]) return true;
            return false;
        }
        gvis[u] = cvis[u] = true;
        bool flg = dfs(d[u].ch[0]) || dfs(d[u].ch[1]);
        cvis[u] = false;
        return flg;
    }
    bool chkCircle () {
        for(int i = 0; i<=dtot; i++)
            if(!gvis[i] && dfs(i)) return true;
        return false;
    }
}
char buf[MAXN];
int main () {
    int N;
    scanf("%d", &N);
    for(int i = 1; i<=N; i++) {
        scanf("%s", buf);
        Trie :: insert(buf);
    }
    Trie :: setup();
    printf("%s\n", Trie :: chkCircle() ? "TAK" : "NIE");
}

BZOJ 1444

题目大意:给你一个按一定概率不断生成字符的机器和N个长为L的字符串, 问每个字符串被第一次匹配的概率, 两位精度。
N和L小于等于10.

解题报告

搞出AC自动机, 像古代猪猡一样高斯消元。
发现没有常数项, 把所有终止节点的概率加起来等于1, 然后拿这个等式换掉根节点的等式, 这样可以保证除了根节点以外其他节点都能消元消出来(因为矩阵g[i][i]不等于0)。
最后上高斯消元即可。
注意特判字符串不可能出现的情况。
吐槽:高斯消元好久没写了…姿势不是很对…精度写炸搞了好久…

样例

Input:10 10 10
1 17
3 17
2 17
1 17
0 17
5 17
2 17
1 17
1 17
1 17
AAABABDGAA
ACHHCCDHAC
AAIJFCHHDB
AACDBBBDCG
BFFCAAIGJH
ACGBBEJJHA
DEDDBAACCH
AACCDBCHAH
DDBDAACCEF
HGFGAHGDCC
Output:
0.02
0.02
0.04
0.28
0.39
0.00
0.00
0.03
0.00
0.21

代码 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <climits>
#include <queue>
#include <cmath>
using namespace std;
typedef unsigned long long ULL;
const int MAXN = 12;
const double EPS = 1e-6;
int M;
double posb[30];
inline bool equal (double a, double b) {return fabs(a-b) <= EPS;}
namespace Trie {
    const int MAXD = MAXN*MAXN;
    struct Node {
        int ch[26];
        int pre;
        bool mark;
    } d[MAXD];
    int dtot;
    int insert (char * str) {
        int u = 0;
        while(*str != '\0') {
            if(!d[u].ch[*str-'A'])
                d[u].ch[*str-'A'] = ++dtot;
            u = d[u].ch[*str-'A'];
            ++ str;
        }
        d[u].mark = true;
        return u;
    }
    queue<int> que;
    void setup () {
        que.push(0);
        while(!que.empty()) {
            int u = que.front();
            que.pop();
            for(int ch = 0; ch < M; ch ++) {
                if(d[u].ch[ch]) {
                    int v = d[u].ch[ch];
                    if(d[u].pre != u)
                        d[v].pre = d[d[u].pre].ch[ch];
                    que.push(v);
                } else d[u].ch[ch] = d[d[u].pre].ch[ch];
            }
        }
    }
    double g[MAXD][MAXD];
    bool vis[MAXD];
    void genMatrix () {
        for(int i = 0; i<=dtot; i++) {
            if(d[i].mark) continue ;
            for(int ch = 0; ch < M; ch++)
                g[d[i].ch[ch]][i] += posb[ch];
        }
        for(int i = 0; i<=dtot; i++)
            g[i][i] -= 1.0;
        for(int i = 0; i<=dtot; i++)
            if(d[i].mark) g[0][i] = 1.0;
            else g[0][i] = 0.0;
        g[0][dtot+1] = 1.0;
    }
    void gauss () {
        for(int col = 0; col<=dtot; col++) {
            int p = -1;
            for(int row = 0; row<=dtot; row++)
                if(!vis[row] && !equal(g[row][col], 0.0)) {p = row; break;}
            if(p == -1) continue ;
            vis[p] = true;
            for(int row = 0; row<=dtot; row++)
                if(row != p) {
                    double t = g[row][col]/g[p][col];
                    for(int i = col; i<=dtot+1; i++)
                        g[row][i] -= g[p][i]*t;
                }
        }
    }
}
int pos[MAXN];
int main () {
    int N, L;
    scanf("%d%d%d", &N, &L, &M);
    for(int i = 0; i<M; i++) {
        int p, q;
        scanf("%d%d", &p, &q);
        posb[i] = (double)p/q;
    }
    for(int i = 1; i<=N; i++) {
        char buf[50];
        scanf("%s", buf);
        bool flg = true;
        for(int j = 0; j<L; j++)
            if(equal(posb[buf[j]-'A'], 0.0)) {flg = false; break;}
        if(!flg) continue;
        pos[i] = Trie :: insert(buf);
    }
    Trie :: setup();
    Trie :: genMatrix();
    Trie :: gauss();
    for(int i = 1; i<=N; i++) {
        if(pos[i] == 0) {puts("0.00"); continue ;}
        int x = -1;
        for(int j = 0; j<=Trie :: dtot; j++)
            if(!equal(Trie :: g[j][pos[i]], 0)) {x = j; break;}
        if(x == -1) {puts("0.00"); continue ;}
        double a = Trie :: g[x][Trie :: dtot+1];
        double b = Trie :: g[x][pos[i]];
        printf("%.2lf\n", a/b);
    }
}

BZOJ 3881

有N个字符串S 1 ,S 2 …S n , 有一个字符串集合T, 一开始集合是空的。
接下来会发生Q个操作, 操作有两种形式:
“1 P”，往集合里添加一个字符串P。
“2 x”，询问集合T中有多少个字符串包含串S x 。（我们称串A包含串B，当且仅当B是A的子串）

解题报告

比较猥琐的题目..
首先对所有S建AC自动机, 发现加入一个字符串P相当于把P放到S里面跑一遍, 并且把所有匹配串+1.
暴力跑可以被卡到N*L。
对AC自动机的fail链建树, 每次跑P串时把所有到达过的节点扔到一个栈内, 那么跑完后所有栈内节点到跟的路径形成的子图中所有的终止节点对应的字符串都应当+1。
用虚树和树状数组维护这个东西, 每次跑完P串用树剖LCA对栈内节点建虚树, 容斥一下子树和, 用树状数组维护。
吐槽: 不小心手残把Trie结构体内的ch数组开成char型…小数据看不出, 手造大数据才发现…

代码 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <climits>
#include <queue>
#include <cmath>
#include <map>
using namespace std;
typedef unsigned long long ULL;
const int MAXN = 100010;
const int MAXL = 2000020+MAXN;

namespace DfnQry {
    struct Node {
        int v, nxt;
    } d[MAXL];
    int head[MAXL], etot;
    void addEdge (int a, int b) {
        etot ++;
        d[etot].v = b;
        d[etot].nxt = head[a];
        head[a] = etot;
    }
    int dfn[MAXL], dfnlst[MAXL], dfntot;
    int rev[MAXL], dep[MAXL], fa[MAXL], sz[MAXL];
    void dfs (int u) {
        sz[u] = 1;
        rev[dfn[u] = ++dfntot] = u;
        for(int e = head[u]; e; e = d[e].nxt) {
            dep[d[e].v] = dep[u]+1;
            fa[d[e].v] = u;
            dfs(d[e].v);
            sz[u] += sz[d[e].v];
        }
        dfnlst[u] = dfntot;
    }
    int top[MAXL];
    void chainDiv (int u) {
        if(!top[u]) top[u] = u;
        int mxp = 0;
        for(int e = head[u]; e; e = d[e].nxt)
            if(sz[d[e].v] > sz[mxp]) mxp = d[e].v;
        if(!mxp) return ;
        top[mxp] = top[u];
        chainDiv(mxp);
        for(int e = head[u]; e; e = d[e].nxt)
            if(d[e].v != mxp) chainDiv(d[e].v);
    }
    int getLCA (int a, int b) {
        while(top[a] != top[b]) {
            if(dep[top[a]] > dep[top[b]] ) a = fa[top[a]];
            else b = fa[top[b]];
        }
        if(dep[a] < dep[b]) return a;
        return b;
    }
    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;
    }
    int stk[MAXL], stktop;
    inline void feed (int x) {stk[++stktop] = dfn[x];}
    inline void digest () {
        std :: sort(stk+1, stk+stktop+1);
        add(stk[1], 1);
        for(int i = 2; i<=stktop; i++) {
            add(stk[i], 1);
            int lca = getLCA(rev[stk[i-1]], rev[stk[i]]);
            add(dfn[lca], -1);
        }
        stktop = 0;
    }
    inline 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;
    inline int insert (char * str) {
        int u = 0;
        while(*str != '\0') {
            if(!d[u].ch[*str-'a'])
                d[u].ch[*str-'a'] = ++dtot;
            u = d[u].ch[*str-'a'];
            ++ str;
        }
        return u;
    }
    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]) {
                    int v = d[u].ch[ch];
                    if(d[u].pre != u)
                        d[v].pre = d[d[u].pre].ch[ch];
                    que.push(v);
                } else d[u].ch[ch] = d[d[u].pre].ch[ch];
        }
    }
    inline void build () {
        for(int i = 1; i<=dtot; i++)
            DfnQry :: addEdge(d[i].pre+1, i+1);
        DfnQry :: dfs(1);
        DfnQry :: chainDiv(1);
    }
    inline int query (int u) {return DfnQry :: query(u+1);}
    void match (char * str) {
        int u = 0;
        while(*str != '\0') {
            u = d[u].ch[*str - 'a'];
            DfnQry :: feed(u+1);
            ++ str;
        }
        DfnQry :: digest();
    }
}

char buf[MAXL];
int qpos[MAXN];
int main () {
    freopen("data.in", "r", stdin);
    int N;
    scanf("%d", &N);
    for(int i = 1; i<=N; i++) {
        scanf("%s", buf);
        qpos[i] = Trie :: insert(buf);
    }
    Trie :: setup();
    Trie :: build();
    int Q;
    scanf("%d", &Q);
    while(Q --) {
        int ord;
        scanf("%d", &ord);
        if(ord == 1) {
            scanf("%s", buf);
            Trie :: match(buf);
        } else {
            int p;
            scanf("%d", &p);
            printf("%d\n", Trie :: query(qpos[p]));
        }
    }
}

/*
int main () {
    freopen("data.in", "w", stdout);
    printf("1\n");
    for(int i = 1; i<=2000000; i++)
        putchar('a');
    printf("\n2\n1 ");
    for(int i = 1; i<=2000000; i++)
        putchar('a');
    printf("\n2 1\n");
}
*/

BZOJ 2754

题目大意: N只猫, 每只猫有名和性, 老师会进行M次点名, 每次询问一个字符串, 性或者名包含这个字符串的猫必须回答, 问每个点名回答的猫数量和点名完成后每只猫回答的次数。
这里字符串字符集大小为1w.

解题报告

用map+AC自动机水过啊..字符串排序构建Trie+二分儿子应该也可以。
每次都忘记调用 setup() 函数…本来可以一次AC, 调试了10min…

代码 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <climits>
#include <queue>
#include <map>
using namespace std;
typedef unsigned long long ULL;
const int ENDNUM = -78619472;
namespace Trie {
    const int MAXD = 100100;
    struct Node {
        map<int, int> ch;
        int pre;
        bool mark;
        vector<int> eid;
    } d[MAXD];
    int dtot = 0;
    inline void insert (vector<int> :: iterator str, int id) {
        int u = 0;
        while(*str != ENDNUM) {
            if(d[u].ch.find(*str) == d[u].ch.end())
                d[u].ch[*str] = ++dtot;
            u = d[u].ch[*str];
            ++ str;
        }
        d[u].eid.push_back(id);
        d[u].mark = true;
    }
    queue<int> que;
    void setup () {
        que.push(0);
        while(!que.empty()) {
            int u = que.front();
            que.pop();
            for(map<int, int> :: iterator it = d[u].ch.begin(); it != d[u].ch.end(); it++) {
                int v = it->second;
                int k = d[u].pre;
                while(k && d[k].ch.find(it->first) == d[k].ch.end()) k = d[k].pre;
                //printf("v:%d, u:%d, k:%d\n", v, u, k);
                if(d[k].ch.find(it->first) != d[k].ch.end() && k != u)
                    d[v].pre = d[k].ch[it->first];
                d[v].mark |= d[d[v].pre].mark;
                que.push(v);
            }
        }
    }
    int tag[MAXD];
    int ans[MAXD];
    int countans (int u, int tg) {
        int ret = 0;
        while(d[u].mark) {
            if(tag[u] == tg) return ret;
            tag[u] = tg;
            ret += d[u].eid.size();
            for(int i = 0; i<(int)d[u].eid.size(); i++)
                ans[d[u].eid[i]] ++;
            u = d[u].pre;
        }
        return ret;
    }
    int feed (vector<int> :: iterator str, int cid) {
        int u = 0, ret = 0;
        while(*str != ENDNUM) {
            if(d[u].ch.find(*str) == d[u].ch.end()) {
                if(!u) ++ str;
                else u = d[u].pre;
            } else {
                u = d[u].ch[*str];
                ret += countans(u, cid);
                ++str;
            }
        }
        return ret;
    }
}
void inputStr (vector<int> & vc) {
    vc.clear();
    int x, a;
    scanf("%d", &x);
    for(int i = 1; i<=x; i++) {
        scanf("%d", &a);
        vc.push_back(a);
    }
    vc.push_back(ENDNUM);
}
vector<int> nfirst[20020], nsecond[20020];
vector<int> qry;
int ans2[50050];
int main () {
    int N, M;
    scanf("%d%d", &N, &M);
    for(int i = 1; i<=N; i++) {
        inputStr(nfirst[i]);
        inputStr(nsecond[i]);
    }
    for(int i = 1; i<=M; i++) {
        inputStr(qry);
        Trie :: insert(qry.begin(), i);
    }
    Trie :: setup();
    for(int i = 1; i<=N; i++) {
        ans2[i] += Trie :: feed(nfirst[i].begin(), i);
        ans2[i] += Trie :: feed(nsecond[i].begin(), i);
    }
    for(int i = 1; i<=M; i++)
        printf("%d\n", Trie :: ans[i]);
    for(int i = 1; i<=N; i++)
        printf("%d%c", ans2[i], (i==N) ? '\n' : ' ');
}

BZOJ 3172

题目大意: 给你n个小写字母串, 分别为a,b,c…问用这N个串拼接起来的串”a#b#c#…”中每个串出现了多少次。

解题报告

当然可以用AC自动机大模拟…
更加优雅的做法就是直接在fail树上乱搞:

代码 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <climits>
#include <queue>
#include <map>
using namespace std;
typedef unsigned long long ULL;
namespace Trie {
    const int MAXD = 1000010;
    struct Node {
        int ch[26];
        int pre;
        int sum, ans;
    } d[MAXD];
    int dtot;
    int insert (char * str) {
        int u = 0;
        while(*str != '\0') {
            if(d[u].ch[*str-'a'] == 0)
                d[u].ch[*str-'a'] = ++dtot;
            u = d[u].ch[*str-'a'];
            d[u].sum++;
            ++ str;
        }
        return u;
    }
    struct Node2 {
        int v, nxt;
    } adj[MAXD];
    int head[MAXD], etot;
    inline void addEdge (int a, int b) {
        etot ++;
        adj[etot].v = b;
        adj[etot].nxt = head[a];
        head[a] = etot;
    }
    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(u != d[u].pre)
                        d[v].pre = d[d[u].pre].ch[ch];
                    addEdge(d[v].pre, v);
                    que.push(v);
                } else d[u].ch[ch] = d[d[u].pre].ch[ch];
        }
    }
    void dfs (int u) {
        for(int e = head[u]; e; e = adj[e].nxt)
            dfs(adj[e].v), d[u].ans += d[adj[e].v].ans;
        d[u].ans += d[u].sum;
    }
}
char buf[1000010];
int pos[210];
int main () {
    int N;
    scanf("%d", &N);
    for(int i = 1; i<=N; i++) {
        scanf("%s", buf);
        pos[i] = Trie :: insert(buf);
    }
    Trie :: setup();
    Trie :: dfs(0);
    for(int i = 1; i<=N; i++)
        printf("%d\n", Trie :: d[pos[i]].ans);
}

BZOJ 1030

题目大意:给N个模式串, 问用A-Z组成的长度为L的字符串中出现了至少一个模式串的串数量。
模式串总长≤6000, L≤100

解题报告

一开始吧总长读成100…矩阵快速幂, RE
后来瞅了一眼别人的代码才发现题目理解错误..
然后在AC自动机上写DP, wa
发现自己ZZ了, 又忘记下传终止标记了..
一定要记住下传终止标记!

代码 

#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 = 110;
const int MOD = 10007;

struct Node2 {
    int v, nxt;
} adj[MAXL*60*26];
int head[MAXL*60], etot;
void addEdge (int a, int b) {
    etot ++;
    adj[etot].v = b;
    adj[etot].nxt = head[a];
    head[a] = etot;
}

namespace Trie {
    const int MAXD = MAXL*60;
    struct Node {
        int ch[26];
        int pre;
        bool mark;
    } d[MAXD];
    int dtot;
    void insert (char * str) {
        int u = 0;
        while(*str != '\0') {
            if(d[u].ch[*str-'A'] == 0)
                d[u].ch[*str-'A'] = ++dtot;
            u = d[u].ch[*str-'A'];
            ++ str;
        }
        d[u].mark = true;
    }
    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 |= d[d[v].pre].mark;
                    que.push(v);
                } else d[u].ch[ch] = d[d[u].pre].ch[ch];
            }
            if(!d[u].mark) for(int ch = 0; ch<26; ch++) addEdge(u, d[u].ch[ch]);
            else for(int i = 1; i<=26; i++) addEdge(u, dtot+1);
        }
        for(int i = 1; i<=26; i++) addEdge(dtot+1, dtot+1);
    }

    int dp[110][6060];
    int solve (int len) {
        dp[0][0] = 1;
        for(int i = 0; i<len; i++)
            for(int u = 0; u<=dtot+1; u++)
                for(int e = head[u]; e; e = adj[e].nxt)
                    (dp[i+1][adj[e].v] += dp[i][u]) %= MOD;
        int ret = 0;
        for(int i = 1; i<=dtot; i++)
            if(d[i].mark) ret += dp[len][i];
        return (ret+dp[len][dtot+1])%MOD;
    }
}
char buf[MAXL];
int main () {
    int N, L;
    scanf("%d%d", &N, &L);
    if(N == 0 || L == 0) {puts("0"); return 0;}
    for(int i = 1; i<=N; i++) {
        scanf("%s", buf);
        Trie :: insert(buf);
    }
    Trie :: setup();
    printf("%d\n", Trie :: solve(L));
}

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

评论列表

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

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

Join the discussion

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

！

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