QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #706477 | #243. Lyndon Substring | TheZone | 100 ✓ | 262ms | 22900kb | C++20 | 4.5kb | 2024-11-03 11:38:16 | 2024-11-03 11:38:16 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=100010,base=41,mod=1e9+9;
string s[N];
int maxx[N],pw[N];
vector<int>las[N];
vector<pair<int,int> >lyndon[N];
struct hs{
vector<int>p;
void set(string& s){
int n=s.length();
p.resize(n);
p[0]=s[0];
for(int i=1;i<=n-1;i++){
p[i]=(1ll*p[i-1]*base+s[i])%mod;
}
}
int get(int l,int r){
if(l==0){
return p[r];
}
return (p[r]-1ll*p[l-1]*pw[r-l+1]%mod+mod)%mod;
}
}p[N];
void Lyndon(int i,string& s){
int n=s.length(),x=0,y,z;
maxx[i]=0;
las[i].clear();
lyndon[i].clear();
while(x<=n-1){
y=x;
z=x+1;
while(s[y]<=s[z]){
if(s[y]==s[z]){
y++;
z++;
}
else{
y=x;
z++;
}
}
if(z==n){
las[i].push_back(x);
}
while(x<=y){
lyndon[i].push_back({x,x+z-y-1});
x+=(z-y);
}
maxx[i]=max(maxx[i],z-y);
}
las[i].push_back(n);
}
int calc(int x,int y,int a,int len){
if(a+len-1<s[x].length()){
return p[x].get(a,a+len-1);
}
if(a>=s[x].length()){
return p[y].get(a-s[x].length(),a-s[x].length()+len-1);
}
return (1ll*p[x].get(a,s[x].length()-1)*pw[a+len-s[x].length()]%mod+p[y].get(0,a-s[x].length()+len-1))%mod;
}
char get(int x,int y,int a){
if(a<s[x].length()){
return s[x][a];
}
return s[y][a-s[x].length()];
}
bool check(int x,int y,int a,int b,int len){
int l=1,r=len,mid,ans=0;
if(calc(x,y,a,len)==calc(x,y,b,len)){
return 0;
}
while(l<=r){
mid=(l+r)>>1;
if(calc(x,y,a,mid)==calc(x,y,b,mid)){
l=mid+1;
ans=mid;
}
else{
r=mid-1;
}
}
return get(x,y,a+ans)<get(x,y,b+ans);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t,n,m,x,y,a,b,now,ans,l,r,mid,anss;
cin>>t;
pw[0]=1;
for(int i=1;i<=100000;i++){
pw[i]=1ll*pw[i-1]*base%mod;
}
while(t--){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s[i];
Lyndon(i,s[i]);
p[i].set(s[i]);
}
while(m--){
cin>>x>>y;
now=-1;
ans=max(maxx[x],maxx[y]);
for(int i=0;i<las[x].size()-1;i++){
a=las[x][i];
b=las[x][i+1];
if(check(x,y,a,b,s[x].length()-b+s[y].length())){
now=a;
break;
}
}
if(now!=-1){
l=0;
r=lyndon[y].size()-1;
while(l<=r){
mid=(l+r)>>1;
if(check(x,y,now,s[x].length()+lyndon[y][mid].first,lyndon[y][mid].second-lyndon[y][mid].first+1)){
l=mid+1;
anss=lyndon[y][mid].second+1;
}
else{
r=mid-1;
}
}
ans=max(ans,(int)s[x].length()-now+anss);
}
cout<<ans<<"\n";
}
}
}
/*#include<bits/stdc++.h>
using namespace std;
const int N=100010,base=41,mod=1e9+9;
string s[N];
int maxx[N],pw[N];
vector<int>las[N];
vector<pair<int,int> >lyndon[N];
struct hs{
vector<int>p;
void set(string& s){
int n=s.length();
p.resize(n);
p[0]=s[0];
for(int i=1;i<=n-1;i++){
p[i]=(1ll*p[i-1]*base+s[i])%mod;
}
}
int get(int l,int r){
if(l==0){
return p[r];
}
return (p[r]-1ll*p[l-1]*pw[r-l+1]%mod+mod)%mod;
}
}p[N];
void Lyndon(int i,string& s){
int n=s.length(),x=0,y,z;
maxx[i]=0;
las[i].clear();
lyndon[i].clear();
while(x<=n-1){
y=x;
z=x+1;
while(s[y]<=s[z]){
if(s[y]==s[z]){
y++;
z++;
}
else{
y=x;
z++;
}
}
if(z==n){
las[i].push_back(x);
}
while(x<=y){
lyndon[i].push_back({x,x+z-y-1});
x+=(z-y);
}
maxx[i]=max(maxx[i],z-y);
}
las[i].push_back(n);
}
int calc(int x,int y,int a,int len){
if(a+len-1<s[x].length()){
return p[x].get(a,a+len-1);
}
if(a>=s[x].length()){
return p[y].get(a-s[x].length(),a-s[x].length()+len-1);
}
return (1ll*p[x].get(a,s[x].length()-1)*pw[a+len-s[x].length()]%mod+p[y].get(0,a-s[x].length()+len-1))%mod;
}
char get(int x,int y,int a){
if(a<s[x].length()){
return s[x][a];
}
return s[y][a-s[x].length()];
}
bool check(int x,int y,int a,int b,int len){
int l=1,r=len,mid,ans=0;
if(calc(x,y,a,len)==calc(x,y,b,len)){
return 0;
}
while(l<=r){
mid=(l+r)>>1;
if(calc(x,y,a,mid)==calc(x,y,b,mid)){
l=mid+1;
ans=mid;
}
else{
r=mid-1;
}
}
return get(x,y,a+ans)<get(x,y,b+ans);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t,n,m,x,y,a,b,now,ans,l,r,mid,anss;
cin>>t;
pw[0]=1;
for(int i=1;i<=100000;i++){
pw[i]=1ll*pw[i-1]*base%mod;
}
while(t--){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s[i];
Lyndon(i,s[i]);
p[i].set(s[i]);
}
while(m--){
cin>>x>>y;
now=-1;
ans=max(maxx[x],maxx[y]);
for(int i=0;i<las[x].size()-1;i++){
}
}
}*/
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 100
Accepted
time: 262ms
memory: 22900kb
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:
ok 600000 lines