宁波自适应网站建设,市场营销活动策划方案,wordpress 导航栏 搜索,中国做外贸最好的网站正题
题目链接:https://www.luogu.com.cn/problem/P2408 题目大意
给出一个字符串#xff0c;求有多少个不同的子串。 解题思路
进行后缀排序之后#xff0c;对于位置iii他有n−i1n-i1n−i1个后缀#xff0c;然后它和排在它前面的后缀有heightiheight_iheighti个重复的…正题
题目链接:https://www.luogu.com.cn/problem/P2408 题目大意
给出一个字符串求有多少个不同的子串。 解题思路
进行后缀排序之后对于位置iii他有n−i1n-i1n−i1个后缀然后它和排在它前面的后缀有heightiheight_iheighti个重复的前缀也就是这么多个重复的子串。对于更前面的后缀的重复在刚刚那一个那里已经减去过了所以不用统计。
所以答案就是∑i1nn−i1−heightsai\sum_{i1}^nn-i1-height_{sa_i}∑i1nn−i1−heightsai codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e510;
ll n,m,sa[N],x[N],y[N],c[N],h[N],rk[N],ans;
char s[N];
void Qsort(){for(ll i1;im;i)c[i]0;for(ll i1;in;i)c[x[i]];for(ll i1;im;i)c[i]c[i-1];for(ll in;i1;i--)sa[c[x[y[i]]]--]y[i],y[i]0;return;
}
void SA(){m26;for(ll i1;in;i)x[i]s[i]-a1,y[i]i;Qsort();for(ll w1;wn;w1){ll p0; for(ll in-w1;in;i)y[p]i;for(ll i1;in;i)if(sa[i]w)y[p]sa[i]-w;Qsort();swap(x,y);x[sa[1]]p1;for(ll i2;in;i)x[sa[i]](y[sa[i]]y[sa[i-1]]y[sa[i]w]y[sa[i-1]w])?p:p;if(pn)break;mp;}return;
}
void Get_height(){ll k0;for(ll i1;in;i)rk[sa[i]]i;for(ll i1;in;i){if(rk[i]1)continue;if(k)k--;ll jsa[rk[i]-1];while(iknjkns[ik]s[jk])k;h[rk[i]]k;}return;
}
int main()
{scanf(%lld,n);scanf(%s,s1);SA();Get_height();for(ll i1;in;i)ansn-i1-h[sa[i]];printf(%lld,ans);
}
