QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#124491#552. 字符串匹配问题GoatGirl98#0 0ms0kbC++143.8kb2023-07-14 23:24:542023-07-14 23:24:55

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-14 23:24:55]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2023-07-14 23:24:54]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define sin sinl
#define cos cosl
#define acos acosl
const int N = 3e5 + 9;
const int mod = 1e9 + 7;

const double PI = acos(-1);
struct base
{
    double a, b;
    base(double a = 0, double b = 0) : a(a), b(b) {}
    const base operator+(const base &c) const
    {
        return base(a + c.a, b + c.b);
    }
    const base operator-(const base &c) const
    {
        return base(a - c.a, b - c.b);
    }
    const base operator*(const base &c) const
    {
        return base(a * c.a - b * c.b, a * c.b + b * c.a);
    }
};
void fft(vector<base> &p, bool inv = 0)
{
    int n = p.size(), i = 0;
    for (int j = 1; j < n - 1; ++j)
    {
        for (int k = n >> 1; k > (i ^= k); k >>= 1)
            ;
        if (j < i)
            swap(p[i], p[j]);
    }
    for (int l = 1, m; (m = l << 1) <= n; l <<= 1)
    {
        double ang = 2 * PI / m;
        base wn = base(cos(ang), (inv ? 1. : -1.) * sin(ang)), w;
        for (int i = 0, j, k; i < n; i += m)
        {
            for (w = base(1, 0), j = i, k = i + l; j < k; ++j, w = w * wn)
            {
                base t = w * p[j + l];
                p[j + l] = p[j] - t;
                p[j] = p[j] + t;
            }
        }
    }
    if (inv)
        for (int i = 0; i < n; ++i)
            p[i].a /= n, p[i].b /= n;
}
vector<int> multiply(vector<int> &a, vector<int> &b)
{
    int n = a.size(), m = b.size(), t = n + m - 1, sz = 1;
    while (sz < t)
        sz <<= 1;
    vector<base> x(sz), y(sz), z(sz);
    for (int i = 0; i < sz; ++i)
    {
        x[i] = i < a.size() ? base(a[i], 0) : base(0, 0);
        y[i] = i < b.size() ? base(b[i], 0) : base(0, 0);
    }
    fft(x), fft(y);
    for (int i = 0; i < sz; ++i)
        z[i] = x[i] * y[i];
    fft(z, 1);
    vector<int> ret(sz);
    for (int i = 0; i < sz; ++i)
        ret[i] = z[i].a + 0.5;
    while (ret.size() > 1 && ret.back() == 0)
        ret.pop_back();
    return ret;
}
// find occurrences of t in s where '?'s are automatically matched with any character
// res[i + m - 1] = sum_j=0 to m - 1_{s[i + j] * t[j] * (s[i + j] - t[j])
vector<int> string_matching(string &s, string &t)
{
    int n = s.size(), m = t.size();
    vector<int> s1(n), s2(n), s3(n);
    for (int i = 0; i < n; i++)
        s1[i] = s[i] == '*' ? 0 : s[i] - 'a' + 1; // assign any non zero number for non '?'s
    for (int i = 0; i < n; i++)
        s2[i] = s1[i] * s1[i];
    for (int i = 0; i < n; i++)
        s3[i] = s1[i] * s2[i];
    vector<int> t1(m), t2(m), t3(m);
    for (int i = 0; i < m; i++)
        t1[i] = t[i] == '*' ? 0 : t[i] - 'a' + 1;
    for (int i = 0; i < m; i++)
        t2[i] = t1[i] * t1[i];
    for (int i = 0; i < m; i++)
        t3[i] = t1[i] * t2[i];
    reverse(t1.begin(), t1.end());
    reverse(t2.begin(), t2.end());
    reverse(t3.begin(), t3.end());
    vector<int> s1t3 = multiply(s1, t3);
    vector<int> s2t2 = multiply(s2, t2);
    vector<int> s3t1 = multiply(s3, t1);
    vector<int> res(n);
    for (int i = 0; i < n; i++)
        res[i] = s1t3[i] - s2t2[i] * 2 + s3t1[i];
    vector<int> oc;
    for (int i = m - 1; i < n; i++)
        if (res[i] == 0)
            oc.push_back(i - m + 1);
    return oc;
}
int32_t main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t, m, n;
    t = 1;
    while (t--)
    {
        cin >> m >> n;
        string a, b;
        cin >> a >> b;
        auto ans = string_matching(b, a);
        if (ans.empty())
            cout << "0\n";
        else
        {
            cout << ans.size() << endl;
            for (auto x : ans)
                cout << x + 1 << " ";
        }
        if (t)
            cout << endl;
    }
    return 0;
}

详细

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

cabacacccbacccaabacacaabcabbabcaccbcabbacbcb
aaaccabacaaabb*abaaaa*bcabacacccba*ccaabacadaabcabba*kac*b*abbacabacacccbacccaa*acacaabcabbabca***cabbacbcbcabbacbcbbccbcacbaccbacaacc***bbbabccc**bbcbaaaaaabaabaacbc*cbcca*ccbabbacb*caaabcaba*acccbacccaabcabadac*cbacccaabacacaabca**abcucc*cxbbacb*bbacacc...

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%