QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#371879#7780. Dark LaTeX vs. Light LaTeXcomeintocalm#WA 1ms3804kbC++172.6kb2024-03-30 17:33:112024-03-30 17:33:12

Judging History

你现在查看的是最新测评结果

  • [2024-11-25 20:53:52]
  • hack成功,自动添加数据
  • (/hack/1258)
  • [2024-03-30 17:33:12]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3804kb
  • [2024-03-30 17:33:11]
  • 提交

answer

#include <bits/stdc++.h>

const long long P = 1e15 + 37;

auto GetNext(std::string &s, const int n) {
    std::vector<int> nxt(n);
    nxt[0] = -1;
    for (int i = 1, j = -1; i < n; ++i) {
        while (~j && s[i] != s[j + 1])
            j = nxt[j];
        if (s[i] == s[j + 1])
            ++j;
        nxt[i] = j;
    }
    return nxt;
}

auto calc(std::string &s, std::string &t) {
    std::map<long long, int> mp;
    int n = (int)s.length();
    int m = (int)t.length();

    for (int i = 0; i < m; ++i) {
        long long ha = 0;
        for (int j = i; j < m; ++j) {
            ha = (137ll * ha + (t[j] - 'a' + 1)) % P;
            ++mp[ha];
        }
    }

    long long ret = 0;

    std::vector<long long> base(n);
    base[0] = 1;
    for (int i = 1; i < n; ++i)
        base[i] = 137ll * base[i - 1] % P;
    for (int R = 0; R + 1 < n; ++R) {
        std::string o = std::move(s.substr(R + 1, n));
        std::vector<int> nxt = std::move(GetNext(o, n - R));
        std::vector<int> d(R + 1);
        for (int i = 0, j = -1; i < R; ++i) {
            while (~j && s[i] != o[j + 1]) {
                j = nxt[j];
            }
            if (s[i] == o[j + 1])
                ++j;
            if (~j) {
                // printf("i: %d  R: %d  j: %d\n", i, R, j);
                ++d[i - j];
                --d[i + 1];
            }
        }
        for (int i = 1; i < R; ++i) {
            d[i] += d[i - 1];
        }
        long long ha = 0;
        for (int i = R; i > 0; --i) {
            ha = (ha + base[R - i] * (s[i] - 'a' + 1) % P) % P;
            ret += 1ll * mp[ha] * d[i - 1];
            // printf("hash %d  i:%d d[i-1]: %d\n", ha, i, d[i - 1]);
        }
    }

    return ret;
}

auto qwq(std::string &s, std::string &t) {
    std::map<long long, int> mp;
    int n = (int)s.length();
    int m = (int)t.length();

    for (int i = 0; i < m; ++i) {
        int ha = 0;
        for (int j = i; j < m; ++j) {
            ha = (137ll * ha + (t[j] - 'a' + 1)) % P;
            ++mp[ha];
        }
    }

    long long ret = 0;

    for (int i = 0; i < n; ++i) {
        int ha = 0;
        for (int j = i; j < n; ++j) {
            ha = (137ll * ha + (s[j] - 'a' + 1)) % P;
            ret += mp[ha];
        }
    }
    return ret;
}

int main() {
    std::string s, t;
    std::cin >> s >> t;
    long long ans = qwq(s, t);
    ans += calc(s, t);
    std::reverse(s.begin(), s.end());
    std::reverse(t.begin(), t.end());
    ans += calc(t, s);
    // std::cout << calc(s, t) << ' ' << calc(t, s) << ' ' <<  qwq(s, t) << std::endl;
    std::cout << ans << std::endl;
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3804kb

input:

abab
ab

output:

8

result:

ok 1 number(s): "8"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

abab
abaaab

output:

29

result:

ok 1 number(s): "29"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

abcd
abcde

output:

10

result:

ok 1 number(s): "10"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

aaba
ba

output:

6

result:

ok 1 number(s): "6"

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3592kb

input:

babababaaabbaabababbbaabbbababbaaaaa
aaaabbaababbab

output:

1247

result:

wrong answer 1st numbers differ - expected: '1161', found: '1247'