UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#201329#2144. 子串yizhiming1001152ms190164kbC++113.3kb2024-01-23 09:08:152024-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;
}

Details

小提示:点击横条可展开更详细的信息

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