QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#372864 | #7512. Almost Prefix Concatenation | wendyasif | WA | 0ms | 24044kb | C++14 | 3.3kb | 2024-03-31 20:06:08 | 2024-03-31 20:06:20 |
Judging History
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'