【BZOJ 4566】[HAOI2016] 找相同字符

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4566

解题报告

我们可以拿一个串建SAM,把另一个串扔到SAM中匹配一遍
也可以直接把两个串拼一起,然后建SAM,最后遍历一下就好

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 800009;
const int SGZ = 27;
 
int n, m;
char s[N];
 
class Suffix_Automaton{
int cnt, tail, ch[N][SGZ], fail[N], sz[N][2], len[N], head[N], nxt[N], to[N];
public:
    inline void init() {
		cnt = tail = 1;
        for (int i = 1; i <= n; i++) {
            append(s[i] - 'a', 0);
        }
        append(SGZ - 1, -1);
        for (int i = n + 2; i <= n + m + 1; i++) {
            append(s[i] - 'a', 1);
        }
        for (int i = 1; i <= cnt; i++) {
            AddEdge(fail[i], i);
        }
        DFS(0, 0);
    }
    inline LL query() {
        LL ret = 0;
        for (int i = 1; i <= cnt; i++) {
            ret += (LL)(len[i] - len[fail[i]]) * sz[i][0] * sz[i][1];
        }
        return ret;
    } 
private:
    inline void DFS(int w, int f) {
        for (int i = head[w]; i; i = nxt[i]) {
            if (to[i] != f) {
                DFS(to[i], w);
                sz[w][0] += sz[to[i]][0];
                sz[w][1] += sz[to[i]][1];
            }
        }
    }
    inline void AddEdge(int u, int v) {
        static int E = 1;
        to[++E] = v; nxt[E] = head[u]; head[u] = E;
    }
    inline void append(char cc, int t) {
        int w = tail, cur = ++cnt;
        if (t != -1) {
            sz[cur][t] += 1;
        }
        len[cur] = len[tail] + 1;
        for (tail = cur; w && !ch[w][cc]; ch[w][cc] = cur, w = fail[w]);
        if (w) {
            if (len[ch[w][cc]] == len[w] + 1) {
                fail[cur] = ch[w][cc];
            } else {
                int nt = ++cnt, pt = ch[w][cc]; 
                memcpy(ch[nt], ch[pt], sizeof(ch[nt]));
                len[nt] = len[w] + 1;
                fail[nt] = fail[pt];
                fail[cur] = fail[pt] = nt;
                for (; w && ch[w][cc] == pt; ch[w][cc] = nt, w = fail[w]);
            }
        } else {
			fail[cur] = 1;
		}
    } 
}sam;
 
int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    s[n + 1] = 'z' + 1;
    scanf("%s", s + n + 2);
    m = strlen(s + n + 2);
    sam.init();
    printf("%lld\n", sam.query());
    return 0;
}

15 thoughts to “【BZOJ 4566】[HAOI2016] 找相同字符”

  1. I like what you guys are up too. Such clever work and reporting! Keep up the excellent works guys I’ve incorporated you guys to my blogroll. I think it will improve the value of my web site :).

  2. 191216 121510hey there i stumbled upon your website searching about the internet. I wanted to say I enjoy the appear of points around here. Maintain it up will save for certain. 694952

  3. 279115 984667Extremely man or woman speeches want to seat giving observe into couples. Brand new sound system just before unnecessary folks ought to always be mindful of typically senior general rule from public speaking, which is to be the mini. finest man speaches 353585

Leave a Reply

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