ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#201329 | #2144. 子串 | yizhiming | 100 | 1152ms | 190164kb | C++11 | 3.3kb | 2024-01-23 09:08:15 | 2024-01-23 12:22:42 |
answer
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#define int long long
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int N = 2e5+5;
int id,pos[N*2],sz[N*2];
char s[N];
int fa[20][N*2];
struct SAM{
struct aa{
int ch[26],len,fa;
}node[N*2];
int las=1,tot=1;
void ins(int x){
int p = las,np = las = ++tot;
pos[np] = id;
sz[np] = 1;
node[np].len = node[p].len+1;
for(;p&&!node[p].ch[x];p=node[p].fa){
node[p].ch[x] = np;
}
if(!p){
node[np].fa = 1;
}else{
int q = node[p].ch[x];
if(node[p].len+1==node[q].len){
node[np].fa = q;
}else{
int nq = ++tot;
node[nq] = node[q];
node[nq].len = node[p].len+1;
node[q].fa = nq;node[np].fa = nq;
for(;p&&node[p].ch[x]==q;p=node[p].fa){
node[p].ch[x] = nq;
}
}
}
}
struct cc{
int x,y;
bool operator<(const cc&u)const{
return y>u.y;
}
};
vector<cc>ed[N*2];
int sum[N*2];//sum表示当前节点的最小排名,即字典序比他大的字符串的个数+1
int num;
int cnt(int x){
return node[x].len-node[node[x].fa].len;
}
void dfs(int u){
for(auto x:ed[u]){
dfs(x.x);
}
sum[u] = num+1;
num+=node[u].len-node[node[u].fa].len;
}
int a[N*2],S[N*2];
void build(){
for(int i=1;i<=tot;i++){
S[node[i].len]++;
}
for(int i=1;i<=tot;i++){
S[i]+=S[i-1];
}
for(int i=1;i<=tot;i++){
a[S[node[i].len]--] = i;
}
for(int i=tot;i>=1;i--){
int u = a[i];
sz[node[u].fa]+=sz[u];
if(!pos[node[u].fa]){
pos[node[u].fa] = pos[u];
}
}
for(int i=tot;i>=2;i--){
ed[node[i].fa].push_back((cc){i,s[pos[i]+node[node[i].fa].len]-'a'});
}
for(int i=1;i<=tot;i++){
sort(ed[i].begin(),ed[i].end());
}
num = 0;
dfs(1);
for(int i=1;i<=tot;i++){
fa[0][i] = node[i].fa;
// cout<<"I:"<<i<<" "<<node[i].fa<<" "<<node[i].len<<"\n";
}
for(int i=1;i<=19;i++){
for(int j=1;j<=tot;j++){
fa[i][j] = fa[i-1][fa[i-1][j]];
}
}
}
}T;
int n,m;
int a[N],pre[N];
int pla[N];
struct xx{
int l,r;
};
vector<xx>res;
signed main(){
scanf("%s",s+1);
n = strlen(s+1);
for(int i=n;i>=1;i--){
id = i;
T.ins(s[i]-'a');
pla[i] = T.las;
// cout<<"I:"<<"LAS:"<<T.las<<"\n";
}
for(int i=1;i<=n;i++){
a[i] = read();
pre[i] = pre[i-1]+a[i];
}
T.build();
for(int i=1;i<=n;i++){
//越往上排名越大,权值越小,要找最靠上的,排名小于等于权值的
int u = pla[i];
for(int j=19;j>=0;j--){
int y = fa[j][u];
if(y<=1){
continue;
}
if(T.sum[y]<=pre[i+T.node[y].len-1]-pre[i-1]){
u = y;
}
}
int l = T.node[T.node[u].fa].len+1;int r = T.node[u].len;
int ans = 0;
while(l<=r){
int mid = (l+r)/2;
if(T.sum[u]+T.node[u].len-mid<=pre[i+mid-1]-pre[i-1]){
r = mid-1;
ans = mid;
}else{
l = mid+1;
}
}
// cout<<"U:"<<u<<" "<<pla[i]<<" "<<ans<<" "<<T.sum[u]<<"\n";
if(ans&&T.sum[u]+T.node[u].len-ans==pre[i+ans-1]-pre[i-1]){
res.push_back((xx){i,i+ans-1});
}
}
cout<<res.size()<<"\n";
for(auto x:res){
cout<<x.l<<" "<<x.r<<"\n";
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 5ms
memory: 10776kb
input:
eddhceagddbdaeadfezzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz 135 894 525 197 184 248 415 312 228 398 424 704 5...
output:
9 20 28 21 29 23 31 25 32 27 35 30 38 32 40 37 46 39 48
result:
ok 19 numbers
Test #2:
score: 10
Accepted
time: 6ms
memory: 11376kb
input:
cababhaddefeechdcaeebfdheffdcfaefbegaebeahafbhadheaacdagafbcccghddfehhaagafhhfdhcdheghchfdbhfahbdefc...
output:
39 765 833 767 838 770 841 777 850 779 851 781 852 782 853 784 855 806 874 809 875 810 877 814 882 8...
result:
ok 79 numbers
Test #3:
score: 10
Accepted
time: 3ms
memory: 11344kb
input:
cacdcaaadcdaacbcddbccdbaccdacbcabaddaadaccacabbdaccdbdddbcdddbaacddcdcccbcababbadddaccddadddaddcccbc...
output:
110 1 319 253 647 429 578 431 579 434 583 438 588 442 593 444 594 446 596 451 600 452 601 456 605 46...
result:
ok 221 numbers
Test #4:
score: 10
Accepted
time: 24ms
memory: 34716kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
903 8 932 119 1057 178 1111 231 1160 415 1338 419 1345 578 1499 668 1582 684 1595 770 1673 795 1700 ...
result:
ok 1807 numbers
Test #5:
score: 10
Accepted
time: 57ms
memory: 47024kb
input:
aabdbcabcabddaaccaabcdbcdcadbaababababccbabaacccccdbcbdbddbadbbddcadddbaddbdbdbdcaaabdbbccbbadadbbca...
output:
3 110 17851 11334 40746 14930 28575
result:
ok 7 numbers
Test #6:
score: 10
Accepted
time: 60ms
memory: 44508kb
input:
dbddcbaaabaddcaacbcbddaabbbabadbbdcbdbaddcbabaacdcdcdccaccbbddcbdccbbbaabbbbadbaadabdaacdadabcadcadd...
output:
1573 40657 42887 40663 42891 40669 42896 40672 42899 40678 42904 40681 42908 40682 42911 40683 42912...
result:
ok 3147 numbers
Test #7:
score: 10
Accepted
time: 53ms
memory: 44128kb
input:
bcaacbccddcacddyacaadccbaccabdbdaaaabcadbdadcdccbcdacacdbdbabacbaadaddabbddddabbcbcccdaabbdbddabcdbc...
output:
2317 37710 40923 37715 40925 37719 40928 37725 40933 37727 40937 37731 40941 37733 40944 37734 40945...
result:
ok 4635 numbers
Test #8:
score: 10
Accepted
time: 293ms
memory: 123220kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
2 29559 63104 88947 168714
result:
ok 5 number(s): "2 29559 63104 88947 168714"
Test #9:
score: 10
Accepted
time: 357ms
memory: 189368kb
input:
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
4 90135 135863 155071 177352 155440 185439 155842 194241
result:
ok 9 numbers
Test #10:
score: 10
Accepted
time: 294ms
memory: 190164kb
input:
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
3 110013 137452 132017 167846 132029 193124
result:
ok 7 numbers