题意:给你一个字符串,找第k大的子字符串.(考虑相同的字符串) 题解:建sam,先预处理出每个节点的出现次数,然后处理出每个节点下面的出现次数,然后在dfs时判断一下往哪边走即可,注意一下num会爆i
... .
题意:给你一个字符串,找第k大的子字符串.(考虑相同的字符串)
题解:建sam,先预处理出每个节点的出现次数,然后处理出每个节点下面的出现次数,然后在dfs时判断一下往哪边走即可,注意一下num会爆int
//#pragma GCC optimize(2)//#pragma GCC optimize(3)//#pragma GCC optimize(4)//#pragma GCC optimize("unroll-loops")//#pragma comment(linker,"/stack:200000000")//#pragma GCC optimize("Ofast,no-stack-protector")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#include<bits/stdc++.h>#define fi first#define se second#define db double#define mp make_pair#define pb push_back#define pi acos(-1.0)#define ll long long#define vi vector<int>#define mod 998244353#define ld long double//#define C 0.5772156649//#define ls l,m,rt<<1//#define rs m+1,r,rt<<1|1#define pll pair<ll,ll>#define pil pair<int,ll>#define pli pair<ll,int>#define pii pair<int,int>#define ull unsigned long long//#define base 1000000000000000000#define fin freopen("a.txt","r",stdin)#define fout freopen("a.txt","w",stdout)#define fio ios::sync_with_stdio(false);cin.tie(0)inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}template<typename T>inline T const& MAX(T const &a,T const &b){return a>b?a:b;}template<typename T>inline T const& MIN(T const &a,T const &b){return a<b?a:b;}inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c,b>>=1;}return ans;}using namespace std;const ull ba=233;const db eps=1e-7;const ll INF=0x3f3f3f3f3f3f3f3f;const int N=100000+10,maxn=100000+10,inf=0x3f3f3f3f;struct SAM{ int last,cnt; int ch[N<<1][26],fa[N<<1],l[N<<1]; ll sz[N<<1],num[N<<1]; int a[N<<1],c[N<<1],vis[N<<1]; void ins(int c){ int p=last,np=++cnt;last=np;l[np]=l[p]+1; for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np; if(!p)fa[np]=1; else { int q=ch[p][c]; if(l[p]+1==l[q])fa[np]=q; else { int nq=++cnt;l[nq]=l[p]+1; memcpy(ch[nq],ch[q],sizeof(ch[q])); fa[nq]=fa[q];fa[q]=fa[np]=nq; for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq; } } sz[np]=1; } void topo() { for(int i=1;i<=cnt;i++)c[l[i]]++; for(int i=1;i<=cnt;i++)c[i]+=c[i-1]; for(int i=1;i<=cnt;i++)a[c[l[i]]--]=i; } void build(char *s){ int len=strlen(s); last=cnt=1; for(int i=0;i<len;i++)ins(s[i]-'a'); topo(); for(int i=cnt;i;i--)sz[fa[a[i]]]+=sz[a[i]]; sz[1]=0; dfs(1);// for(int i=1;i<=cnt;i++)// {// printf("%d %d ++",i,num[i]);// for(int j=0;j<26;j++)if(ch[i][j])printf("%d ",ch[i][j]);// puts("");// } } void dfs(int u) { vis[u]=1; num[u]=sz[u]; for(int i=0;i<26;i++)if(ch[u][i]) { if(!vis[ch[u][i]])dfs(ch[u][i]); num[u]+=num[ch[u][i]]; } } void cal(int u,int k) { if(k<=0)return ; for(int i=0;i<26;i++)if(ch[u][i]) { if(num[ch[u][i]]>=k) { printf("%c",i+'a');// printf("%d %d %d %c %d/n",u,ch[u][i],num[ch[u][i]],i+'a',k); cal(ch[u][i],k-sz[ch[u][i]]); return ; } else k-=num[ch[u][i]]; } }}sam;char s[N];int main(){ int k; scanf("%s%d",s,&k); sam.build(s); if(sam.num[1]<k)puts("No such line."); else sam.cal(1,k); return 0;}/****************************************/ . .. ...
