QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#663438#552. 字符串匹配问题Qingyyx0 0ms0kbC++202.4kb2024-10-21 15:36:302024-10-21 15:36:30

Judging History

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

  • [2024-10-21 15:36:30]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-10-21 15:36:30]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define enl putchar('\n')
#define all(x) (x).begin(),(x).end()
#define debug(x) printf(" "#x":%d\n",x);
using namespace std;
const int MAXN = 3e5 + 5;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
typedef pair<int, int> pii;
char buf[1 << 21], * p1 = buf, * p2 = buf, obuf[1 << 21], * o = obuf, of[35];
#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline ll qpow(ll a, ll n) { ll res = 1; while (n) { if (n & 1)res = res * a % mod; n >>= 1; a = a * a % mod; }return res; }
template <class T = int>inline T read() { T s = 0, f = 1; char c = gc(); for (; !isdigit(c); c = gc())if (c == '-')f = -1; for (; isdigit(c); c = gc())s = s * 10 + c - '0'; return s * f; }
inline void read(int* a, int n) { for (int i = 1; i <= n; ++i)a[i] = read(); }
inline int inal(char* s) { int n = 0; for (s[0] = gc(); !isalpha(s[0]); s[0] = gc()); for (; isalpha(s[n]); s[++n] = gc()); return s[n] = 0, n; }
inline int instr(char* s) { int n = 0; for (s[0] = gc(); s[0] < 33 || s[0]>126; s[0] = gc()); for (; s[n] >= 33 && s[n] <= 126; s[++n] = gc()); return s[n] = 0, n; }
inline int indi(char* s) { int n = 0; for (s[0] = gc(); !isdigit(s[0]); s[0] = gc()); for (; isdigit(s[n]); s[++n] = gc()); return s[n] = 0, n; }
inline void outd(auto* a, int n) { for (int i = 1; i <= n; ++i)printf("%d ", a[i]); enl; }
int n, m, q;

bitset<MAXN> skip[26], p;
char s[MAXN], t[MAXN];
void solve() {
    read(), read();
    n = instr(s + 1), m = instr(t + 1);
    for (int i = 1; i <= n; ++i)
        if (s[i] != '*') skip[s[i] - 'a'].set(i);
        else for (int j = 0; j < 26; ++j) skip[j].set(i);
    vector<int> ans;
    for (int i = 1; i <= m; ++i) {
        p <<= 1;
        p[1] = 1;
        if (t[i] != '*') p &= skip[t[i] - 'a'];
        if (p.test(n)) ans.push_back(i - n + 1);
    }
    printf("%d\n", ans.size());
    for (int x : ans) printf("%d ", x);
}
signed main(signed argc, char const* argv[]) {
    clock_t c1 = clock();
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    //=============================================================
    int TxT = 1;
    // TxT = read();
    while (TxT--)
        solve();
    //=============================================================
#ifdef LOCAL
    end :
    cerr << "Time Used:" << clock() - c1 << "ms" << endl;
#endif
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

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%