目录

P3181-[HAOI2016]找相同字符

2021-01-02 约 520 字预计阅读 2 分钟次阅读

目录

P3181-[HAOI2016]找相同字符

题目:

题目描述:

给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。

输入格式:

两行，两个字符串s1，s2，长度分别为n1，n2。1 <=n1, n2<= 200000，字符串中只有小写字母

输出格式:

输出一个整数表示答案

样例:

样例输入1:

1
2
aabb
bbaa

样例输出1:

1
10

思路:

实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// Problem: P3181 [HAOI2016]找相同字符
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3181
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)

#include "ybwhead/SAM.h"
#include "ybwhead/ios.h"
CPTH::SAM<> x;
long long ans, ans1;
const int maxn = 8e5;
int cnt[maxn], c[maxn], a[maxn];
void solve(int d, const string &s)
{
    x.clear();
    memset(cnt, 0, sizeof(cnt));
    memset(c, 0, sizeof(c));
    int n = s.size();
    for (auto c : s)
        cnt[x.append(c)] = 1;
    // x = CPTH::SAM<>(s);
    ans1 = 0;
    for (int i = 1; i < x.size(); i++)
        c[x[i].len]++;
    for (int i = 1; i < x.size(); i++)
        c[i] += c[i - 1];
    for (int i = 1; i < x.size(); i++)
        a[c[x[i].len]--] = i;
    for (int i = x.size() - 1; i; i--)
    {
        int p = a[i];
        // cerr << i << " " << a[i] << endl;
        cnt[x[p].pa] += cnt[p];
        ans1 += (ll)(x[p].len - x[x[p].pa].len) * cnt[p] * (n - cnt[p]);
    }

    if (d == -1)
        ans -= (ll)n * (n + 1) * (n - 1) / 2 - ans1;
    else
        ans += (ll)n * (n + 1) * (n - 1) / 2 - ans1;
}
int main()
{
    string s, s1, s2;
    yin >> s >> s1;
    cerr << 111 << endl;
    s2 = s + "~" + s1;
    cerr << 111 << endl;
    reverse(s.begin(), s.end());
    cerr << 111 << endl;
    reverse(s1.begin(), s1.end());
    cerr << 111 << endl;
    reverse(s2.begin(), s2.end());
    cerr << 111 << endl;
    solve(1, s2);
    solve(-1, s);
    solve(-1, s1);
    yout << ans / 2 << endl;
    return 0;
}