QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#372864#7512. Almost Prefix ConcatenationwendyasifWA 0ms24044kbC++143.3kb2024-03-31 20:06:082024-03-31 20:06:20

Judging History

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

  • [2024-03-31 20:06:20]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:24044kb
  • [2024-03-31 20:06:08]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int INF = 9e18;
const int N = 1e6 + 10;
const int mod = 998244353;
typedef pair<int,int>PII;
int n , m , lcp[N];
string s , t;

const int mod1 = 1e9 + 7;
const int mod2 = 1e9 + 9;
const int Base = 131;

int base1[N] , ht1[N] , base2[N] , ht2[N] , hs1[N] , hs2[N];
int suf1[N] , suf2[N] , suf3[N];
int now1[N] , now2[N] , now3[N];

inline void init_hash(int n){
    base1[0] = base2[0] = 1;
    for(int i = 1 ; i <= n ; i ++) base1[i] = base1[i - 1] * Base % mod1;
    for(int i = 1 ; i <= n ; i ++) base2[i] = base2[i - 1] * Base % mod2;
}

int add(int x , int y) {
    x %= mod;
    y %= mod;
    return (x + y) % mod;
}
int reduce(int x , int y) {
    x %= mod;
    y %= mod;
    return ((x - y) % mod + mod) % mod;
}

inline PII get_s(int l,int r){
    int x = ((hs1[r] - hs1[l] * base1[r - l]) % mod1 + mod1) % mod1;
    int y = ((hs2[r] - hs2[l] * base2[r - l]) % mod2 + mod2) % mod2;
    return {x , y};
}

inline PII get_t(int l,int r){
    int x = ((ht1[r] - ht1[l] * base1[r - l]) % mod1 + mod1) % mod1;
    int y = ((ht2[r] - ht2[l] * base2[r - l]) % mod2 + mod2) % mod2;
    return {x , y};
}

signed main(){

    cin >> s >> t;
    n = s.size();
    m = t.size();
    init_hash(max(n , m));

    hs1[0] = hs2[0] = 0;
    for(int i = 1 ; i <= n ; i ++) hs1[i] = (hs1[i - 1] * Base % mod1 + s[i - 1]) % mod1;
    for(int i = 1 ; i <= n ; i ++) hs2[i] = (hs2[i - 1] * Base % mod2 + s[i - 1]) % mod2;

    ht1[0] = ht2[0] = 0;
    for(int i = 1 ; i <= m ; i ++) ht1[i] = (ht1[i - 1] * Base % mod1 + t[i - 1]) % mod1;
    for(int i = 1 ; i <= m ; i ++) ht2[i] = (ht2[i - 1] * Base % mod2 + t[i - 1]) % mod2;

    for(int i = 0 ; i < n ; i ++) {

        int l = i , r = min(i + m - 1 , n - 1) , mid = 0;
        while(l <= r) {
            mid = (l + r) >> 1;
            if(get_s(l , mid + 1) != get_t(l - i , mid + 1 - i)) r = mid - 1;
            else l = mid + 1;
        }

        int ll = l , rr = min(l + m - 1 , n - 1) , midd = 0;

        if(ll > rr) { lcp[i] = ll - i; continue; }
        ll += 1;
        if(ll > rr) { lcp[i] = ll - i; continue; }

        while(ll <= rr) {
            midd = (ll + rr) >> 1;
            if(get_s(ll , midd + 1) != get_t(ll - i , midd + 1 - i)) rr = midd - 1;
            else ll = midd + 1;
        }

        lcp[i] = ll - i;
    }
    suf1[n] = 1;
    for(int i = n - 1 ; i >= 0 ; i -- ){
        int l = i + 1 , r = i + lcp[i];
        now1[i] = reduce(suf1[l] , suf1[r + 1]);
        now2[i] = add(reduce(suf2[l] , suf2[r + 1]) , now1[i]);
        now3[i] = add(add(reduce(suf3[l] , suf3[r + 1]) , 2 * reduce(suf2[l] , suf2[r + 1])) , reduce(suf1[l] , suf1[r + 1]));
        suf1[i] = add(suf1[i + 1] , now1[i]);
        suf2[i] = add(suf2[i + 1] , now2[i]);
        suf3[i] = add(suf3[i + 1] , now3[i]);
    }

    cout << now3[0] << "\n";

    return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

/*
g1[i] i 点所在后缀切割方案数
g2[i] i 点所在后缀切割方案长度和
g3[i] i 点所在后缀切割方案长度平方和

suf1[i] :now1[i] 的后缀和
suf2[i] :now2[i] 的后缀和
suf3[i] :now3[i] 的后缀和
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 24044kb

input:

ababaab
aba

output:

532

result:

wrong answer 1st numbers differ - expected: '473', found: '532'