QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#589399 | #21648. Runs | hwpvector | 10 | 0ms | 9724kb | C++20 | 2.5kb | 2024-09-25 17:41:33 | 2024-09-25 17:41:34 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
struct Bart{
int I,m;
void ini(int Mod) {m=Mod; I=(1ll<<62)/m;}
int operator()(int x) {
int tp=x-((__int128)x*I>>62)*m;
while (tp>=m) tp-=m;
while (tp<0) tp+=m;
return tp;
}
};
const int N=1e6+10;
int lyndon[N],lyndonr[N],n; string s;
struct hash{
int base,mod;
Bart getmod;
int p[N],h[N];
void init(int Base,int Mod,string s) {
base=Base,mod=Mod; getmod.ini(mod); int n=s.size(); --n; p[0]=1;
for (int i=1;i<=n;i++) p[i]=getmod(p[i-1]*base);
for (int i=1;i<=n;i++) h[i]=getmod(h[i-1]*base+s[i]);
}
int gethash(int l,int r) {
// assert(((h[r]-h[l-1]*p[r-l+1]%mod)%mod+mod)%mod==getmod(h[r]-h[l-1]*p[r-l+1]));
return getmod(h[r]-h[l-1]*p[r-l+1]);
}
}h[2];
bool equ(int l1,int r1,int l2,int r2) {
return h[0].gethash(l1,r1)==h[0].gethash(l2,r2)&&h[1].gethash(l1,r1)==h[1].gethash(l2,r2);
}
int lcp(int x,int y) {
if (s[x]!=s[y]) return 0;
int l=0,r=n-max(x,y);
while (l<r) {
int mid=r-((r-l)>>1);
if (equ(x,x+mid,y,y+mid)) l=mid;
else r=mid-1;
} return l+1;
}
int lcpr(int x,int y) {
if (s[x]!=s[y]) return 0;
int l=0,r=min(x,y)-1;
while (l<r) {
int mid=r-((r-l)>>1);
if (equ(x-mid,x,y-mid,y)) l=mid;
else r=mid-1;
} return l+1;
}
bool cmp(int x,int y) {
if (s[x]!=s[y]) return s[x]<s[y];
int l=lcp(x,y);
return s[x+l]<s[y+l];
}
void getlyn() {
lyndon[n]=n;
for (int i=n-1;i>=1;i--) {
if (cmp(i+1,i)) {lyndon[i]=i;continue;}
lyndon[i]=n;
for (int j=lyndon[i+1]+1;j<=n;j=lyndon[j]+1) {
if (cmp(j,i)) {lyndon[i]=j-1; break;}
}
} s[n+1]='z'+1,s[0]='z'+1;
lyndonr[n]=n;
for (int i=n-1;i>=1;i--) {
if (!cmp(i+1,i)) {lyndonr[i]=i;continue;}
lyndonr[i]=n;
for (int j=lyndonr[i+1]+1;j<=n;j=lyndonr[j]+1) {
if (!cmp(j,i)) {lyndonr[i]=j-1; break;}
}
} s[n+1]='a'-1,s[0]='a'-1;
}
vector<array<int,3>> ans;
void getans(int l,int r) {
int R=r+lcp(l,r+1);
int L=l-lcpr(l-1,r);
int p=r-l+1;
if (R-L+1>=p*2) ans.pb({L,R,p});
}
signed main() {
// freopen("data.txt","r",stdin);
// freopen("runs.txt","w",stdout);
ios::sync_with_stdio(0);
cin>>s; n=s.size(); s=" "+s; s[0]='a'-1;
h[0].init(131,1e9+7,s);
h[1].init(13331,998244353,s);
s.pb('a'-1);
getlyn();
for (int i=1;i<=n;i++)
getans(i,lyndon[i]),getans(i,lyndonr[i]),
sort(ans.begin(),ans.end());
ans.erase(unique(ans.begin(),ans.end()),ans.end());
cout<<ans.size()<<'\n';
for (auto [l,r,p]:ans) cout<<l<<' '<<r<<' '<<p<<'\n';
}
详细
Pretests
Final Tests
Test #1:
score: 0
Time Limit Exceeded
input:
luynenolgrtkiqkdbpcoqsjyisilepmrkleqytdfmxrupcartchjwqhekspohcftpmkpfnwtmoqesqxluevqwewgylwgpdbgplwwbsqpigtayqmswjksngymtwulavrpjpomiedsmxtmpheoqogfwhtpdnaflsxwhlkrrnkfmfrcmvqelyjhfdylszqftndcynurbgwnnnrbkjfxioeptfaoervxgzzhovypdvfsiytviysqpzhkeiyibwhjviqjgpblmieugxroykgnloxpyyzzugirqbcwqdicloyulqij...
output:
result:
Test #2:
score: 0
Time Limit Exceeded
input:
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...
output:
result:
Test #3:
score: 0
Time Limit Exceeded
input:
bbccaaababbbbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccaaaba...
output:
result:
Test #4:
score: 0
Time Limit Exceeded
input:
dcbaabcdabcddcbaabcdabcddcbadcbaabcdabcddcbaabcdabcddcbadcbaabcdabcddcbadcbaabcdabcddcbaabcdabcddcbadcbaabcdabcddcbaabcdabcddcbadcbaabcdabcddcbadcbaabcdabcddcbaabcdabcddcbadcbaabcdabcddcbadcbaabcdabcddcbaabcdabcddcbadcbaabcdabcddcbaabcdabcddcbadcbaabcdabcddcbadcbaabcdabcddcbaabcdabcddcbadcbaabcdabcd...
output:
result:
Test #5:
score: 10
Accepted
time: 0ms
memory: 9724kb
input:
dcbaabcdabcddcbaabcdabcddcbadcbaabcdabcddcbaabcdabcddcbadcbaabcdabcddcbadcbaabcdabcddcbaabcdabcddcba
output:
31 1 28 12 1 72 28 4 5 1 5 12 4 12 13 1 13 44 16 13 100 44 16 17 1 17 24 4 24 25 1 25 32 4 29 56 12 32 33 1 33 40 4 40 41 1 41 88 16 44 45 1 45 52 4 52 53 1 53 60 4 60 61 1 61 68 4 68 69 1 69 76 4 73 100 12 76 77 1 77 84 4 84 85 1 88 89 1 89 96 4 96 97 1
result:
ok 32 lines
Test #6:
score: 0
Time Limit Exceeded
input:
bbabaababaababbbbabaababaababbbbabbbabaababaababbbbabaababaababbbbabbbabaababaababbbbabbbabaababaababbbbabaababaababbbbabbbabaababaababbbbabaababaababbbbabbbabaababaababbbbabbbabaababaababbbbabaababaababbbbabbbabaababaababbbbabbbabaababaababbbbabaababaababbbbabbbabaababaababbbbabaababaababbbbabbbaba...
output:
result:
Test #7:
score: 0
Time Limit Exceeded
input:
ghbaahxvveloseywqeuokpraqgyscdcimfioohjjnwyhdyftczjorapjhncjqetfjetxnfidbgkeesajrjxkkmutayescxxndtmryuubdgijyisstqefcayeycxccwpfpdypautdbbmblfvexakzakgzpfdrdtytyzkytfdwgqarxvyuvivysbzhgcakxbfwarwvxaufsuzprxjnhenbimlqoncmojkqbgoaiifaegpvdakmhxoplzfamkodtatwghwprerxkhtqhfcofqfqrnsgxgjsgcppmlgfrxdceyuo...
output:
result:
Test #8:
score: 0
Time Limit Exceeded
input:
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...
output:
result:
Test #9:
score: 0
Time Limit Exceeded
input:
aababbbbccabbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccaaaba...
output:
result:
Test #10:
score: 0
Time Limit Exceeded
input:
aababaababbbbabbbabaababaababbbbabbbabaababaababbbbabaababaababbbbabbbabaababaababbbbabbbabaababaababbbbabaababaababbbbabbbabaababaababbbbabaababaababbbbabbbabaababaababbbbabbbabaababaababbbbabaababaababbbbabbbabaababaababbbbabbbabaababaababbbbabaababaababbbbabbbabaababaababbbbabaababaababbbbabbbaba...