QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#149002 | #243. Lyndon Substring | nameless_story | 0 | 242ms | 20144kb | C++20 | 3.5kb | 2023-08-23 21:35:29 | 2023-08-23 21:35:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define N 30'0000
void output(vector<LL> &f){
for (auto x:f) cout<<x<<' '; cout<<endl;
}
const LL B=233,mod=998244353;
LL pw[N];
struct hashstring{
vector<LL> f;
void build(string s){
f.resize(s.size()+1);
f[0]=0;
for (LL i=0;i<s.size();++i){
auto w=s[i];
f[i+1]=(f[i]*B+w)%mod;
}
}
LL calc(LL i,LL len){
return (f[i+len]-f[i]*pw[len]%mod+mod)%mod;
}
};
void init(LL n){
pw[0]=1; for (LL i=1;i<=n;++i) pw[i]=pw[i-1]*B%mod;
}
void solve(){
LL n,m; cin>>n>>m;
vector<string> s(n);
vector<hashstring> f(n);
for (LL i=0;i<n;++i){
cin>>s[i];
f[i].build(s[i]);
}
vector<vector<LL>> lyndon(n),sim(n);
vector<LL> ans(n);
for (LL i=0;i<n;++i){
auto st=s[i]+'0';
for (LL lst=-1,cyc=1,j=1;j<st.size();++j){
if (st[j]>st[j-cyc]) cyc=j-lst;
else{
if (st[j]<st[j-cyc]){
ans[i]=max(ans[i],cyc);
if (j==st.size()-1){
sim[i].push_back(lst+1);
}
for (lst+=cyc;lst<j;lst+=cyc){
lyndon[i].push_back(lst);
}
lst-=cyc;
cyc=1;
j=lst+1;
}
}
}
}
for (LL i=0;i<n;++i){
LL lst=0;
for (LL x:lyndon[i]){
ans[i]=max(ans[i],x-lst);
lst=x;
}
}
auto calc=[&](LL i,LL j,LL p,LL len){
if (p+len<=s[i].size()) return f[i].calc(p,len);
if (p>=s[i].size()) return f[j].calc(p-s[i].size(),len);
LL t=s[i].size()-p;
return (f[i].calc(p,t)*pw[len-t]+f[j].calc(0,len-t))%mod;
};
auto check=[&](LL i,LL j,LL p1,LL p2,LL len){
if (calc(i,j,p1,len)==calc(i,j,p2,len)) return false;
LL l=1,r=len,k=0;
while (l<=r){
LL mid=(l+r)>>1;
if (calc(i,j,p1,mid)==calc(i,j,p2,mid)){
k=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
auto c1=(p1+k<s[i].size())?s[i][p1+k]:s[j][p1+k-s[i].size()];
auto c2=(p2+k<s[i].size())?s[i][p2+k]:s[j][p2+k-s[i].size()];
return c1<c2;
};
while (m--){
LL i,j; cin>>i>>j; --i; --j;
LL tmp=max(ans[i],ans[j]);
LL t=sim[i].back();
for (LL k=0;k+1<sim[i].size();++k){
LL l=1,r=s[j].size();
LL p1=sim[i][k];
LL p2=sim[i][k+1];
LL len0=s[i].size()-p2,mx=0;
if (check(i,j,p1,p2,len0+s[j].size())) t=sim[i][k];
}
if (check(i,j,t,s[i].size(),s[j].size())){
LL l=0,r=lyndon[j].size()-1,pre=0;
while (l<=r){
LL mid=(l+r)>>1;
LL L=mid==0?0:lyndon[j][mid-1]+1;
LL R=lyndon[j][mid];
if (check(i,j,t,s[i].size()+L,R-L+1)){
pre=lyndon[j][mid]+1;
l=mid+1;
}
else{
r=mid-1;
}
}
tmp=max(tmp,(LL)s[i].size()-t+pre);
}
cout<<tmp<<'\n';
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
LL T; cin>>T;
init(200000);
while (T--) solve();
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 242ms
memory: 20144kb
input:
24 100 10000 ab babbab baabbbb abbababbb bb bbbaaaba b aababaa aaabbb abbabbaaa aaaab bbab bbabb baaa bbabbaaba abaa b aabbbb babbbbbb bbaaba aba bbb abbbaabaa aa bbaabaabbb abbbbbb aabbbaabba ababba aabbaab ababa aabbabbaab b aabaabaab baaababa babaaa abaaaabbbb aaaaabaa bbb bbab baaa bbabba ababbb...
output:
2 3 6 11 4 5 3 5 6 8 5 4 4 3 4 2 3 6 10 4 2 5 6 2 8 9 5 7 4 2 7 3 3 6 3 8 6 5 4 3 4 8 3 4 7 2 2 3 9 7 2 2 7 11 3 5 5 8 3 6 6 3 5 4 4 8 4 2 5 8 3 5 5 4 5 3 2 5 3 10 4 5 5 9 4 4 7 3 5 3 5 9 4 4 3 7 8 6 5 3 3 3 6 11 7 8 3 5 6 8 5 7 7 3 7 3 3 6 13 7 3 8 6 3 8 9 5 7 4 3 7 3 3 6 3 8 6 8 7 3 7 8 3 4 10 3 3...
result:
wrong answer 443519th lines differ - expected: '18', found: '12'