QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#194799#7512. Almost Prefix Concatenationucup-team484#WA 11ms17304kbC++202.2kb2023-09-30 22:34:342023-09-30 22:34:35

Judging History

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

  • [2023-09-30 22:34:35]
  • 评测
  • 测评结果:WA
  • 用时:11ms
  • 内存:17304kb
  • [2023-09-30 22:34:34]
  • 提交

answer

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;

const int MAXN = 1000005;
LL mod = 998244353;
LL p = 31, pw[MAXN];
string s, t;
LL h_s[MAXN], h_t[MAXN];
array<array<LL, 3>, MAXN> suf;

LL bpow(LL b, LL x) {

  LL ret = 1;
  while(x) {
    if(x & 1) {
      ret = ret * b % mod;
    }
    b = b * b % mod;
    x /= 2;
  }
  return ret;

}

LL inv(LL x) {
  return bpow(x, mod - 2);
}

void compute_hash(string &s, LL h[]) {
  h[0] = s[0] - 'a' + 1;
  for(int i = 1; i < s.size(); ++i) {
    h[i] = (h[i - 1] + pw[i] * (s[i] - 'a' + 1)) % mod;
  }
}

LL hash_interval(LL h[], int l, int sz) {
  LL ret = h[l + sz - 1] - h[l - 1];
  ret = ret * inv(pw[l]) % mod;
  return ret;
}

int get_next(int ls, int lt) {
  if(ls == s.size() || lt == t.size()) {
    return 0;
  }
  if(s[ls] != t[lt]) {
    return 0;
  }
  int r = min(s.size() - ls + 1, t.size() - lt + 1), l = 0;
  while(l + 1 < r) {
    int m = (l + r) / 2;
    if(hash_interval(h_s, ls, m) != hash_interval(h_t, lt, m)) {
      r = m;
    }
    else l = m;
  }
  //cout << "bs: " << ls << " " << lt << " " << l << " " << r << endl;
  return l;
}

int main() {
    
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> s >> t;
  pw[0] = 1;
  for(int i = 1; i < MAXN; ++i) {
    pw[i] = pw[i - 1] * p % mod;
  }
  compute_hash(s, h_s);
  compute_hash(t, h_t);

  suf[s.size()] = {0, 0, 1};
  for(int i = s.size() - 1; i >= 0; --i) {
    int len = get_next(i, 0);
    if(len < t.size() && i + len < s.size()) {
      ++len;
    }
    //cout << len << endl;
    if(len < t.size() && i + len < s.size()) {
      len = len + get_next(i + len, len);
    }
    auto [a,b,c] = suf[i + 1];
    auto [a2, b2, c2] = suf[i + len + 1];
    LL a3 = (a - a2 + mod) % mod, b3 = (b - b2 + mod) % mod, c3 = (c - c2 + mod) % mod;
    suf[i] = {(a + a3 + 2*b3 + c3) % mod, (b + b3 + c3) % mod, (c3 + c) % mod};
    //cout << i << " len: " << len << " " << suf[i][0] << " " << suf[i][1] << " " << suf[i][2] << endl;
  }
  cout << (suf[0][0] - suf[1][0] + mod) % mod << endl;

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 9ms
memory: 16132kb

input:

ababaab
aba

output:

473

result:

ok 1 number(s): "473"

Test #2:

score: 0
Accepted
time: 4ms
memory: 16440kb

input:

ac
ccpc

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: -100
Wrong Answer
time: 11ms
memory: 17304kb

input:

qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...

output:

948391364

result:

wrong answer 1st numbers differ - expected: '75038697', found: '948391364'