hdu5343 MZL's Circle Zhou

题目描述

MZL's Circle Zhou is good at solving some counting problems. One day, he comes up with a counting problem:

You are given two strings a,b which consist of only lowercase English letters. You can subtract a substring x (maybe empty) from string a and a substring y (also maybe empty) from string b, and then connect them as x+y with x at the front and y at the back. In this way, a series of new strings can be obtained.

The question is how many different new strings can be obtained in this way.

Two strings are different, if and only if they have different lengths or there exists an integer i such that the two strings have different characters at position i.

输入格式

The first line of the input is a single integer T (T≤5), indicating the number of testcases.

For each test case, there are two lines, the first line is string a, and the second line is string b. 1<=|a|,|b|<=90000.

输出格式

For each test case, output one line, a single integer indicating the answer.

样例输入

2
acbcc
cccabc
bbbabbababbababbaaaabbbbabbaaaabaabbabbabbbaaabaab
abbaabbabbaaaabbbaababbabbabababaaaaabbaabbaabbaab

样例输出

135
557539

分析

题目大意:给定两个字符串$a,b$,$x$为$a$的子串,$y$为$b$的字串,求有多少种不同的$x+y$($x+y$不能为空)。

如果把$x+y$整体考虑是没什么思路的。考虑什么时候会出现重复:例如$abcba$可以由$a+bcba$也可以由$ab+cba$拼成,就会出现重复计数。所以我们只需令$x$尽量长,就不会重复计算。

具体做法:对$a,b$分别建立SAM。枚举$x$,若$x$不存在字符$c$的转移,则再枚举以$c$开头的$y$。

观察到我们每次枚举到同一状态时,产生的贡献是一样的,于是我们可以用记忆化搜索做到$O(n)$的复杂度。

代码

#include <bits/stdc++.h>
typedef unsigned long long ull;

const int N = 1e5+50;
const int SIZ = N*2;

struct Sam {
    int top, last;
    int ch[SIZ][26], fa[SIZ], mx[SIZ];

    void clear() {
        last = top = 1;
        memset(ch, 0, sizeof ch);
        memset(fa, 0, sizeof fa);
    }

    void extend(char c) {
        int x = c - 'a', p = last;
        int np = last = ++top;
        mx[np] = mx[p] + 1;
        for (; p && !ch[p][x]; p = fa[p])
            ch[p][x] = np;
        if (!p) {
            fa[np] = 1;
            return;
        }
        int q = ch[p][x];
        if (mx[q] == mx[p] + 1) {
            fa[np] = q;
            return;
        }
        int nq = ++top;
        mx[nq] = mx[p] + 1;
        fa[nq] = fa[q];
        fa[q] = fa[np] = nq;
        memcpy(ch[nq], ch[q], sizeof ch[nq]);
        for (; ch[p][x] == q; p = fa[p])
            ch[p][x] = nq;
    }
} sa, sb;

char a[N], b[N];
ull f1[SIZ], f2[SIZ];

ull dfs2(int u) {
    if (!u) return 0;
    if (f2[u]) return f2[u];
    ull rtn = 1;
    for (int i = 0; i < 26; i++) {
        int v = sb.ch[u][i];
        rtn += dfs2(v);
    }
    return f2[u] = rtn;
}

ull dfs1(int u) {
    if (f1[u]) return f1[u];
    ull rtn = 1;
    for (int i = 0; i < 26; i++) {
        int v = sa.ch[u][i];
        if (v) rtn += dfs1(v);
        else rtn += dfs2(sb.ch[1][i]);
    }
    return f1[u] = rtn;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        sa.clear(); sb.clear();
        memset(f1, 0, sizeof f1);
        memset(f2, 0, sizeof f2);
        scanf("%s%s", a, b);
        for (int len = strlen(a), i = 0; i < len; i++)
            sa.extend(a[i]);
        for (int len = strlen(b), i = 0; i < len; i++)
            sb.extend(b[i]);
        printf("%llu\n", dfs1(1));
    }
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论