P2408 不同子串個數(shù)

題意：

給你一個長為 n 的字符串，求不同的子串的個數(shù)。

我們定義兩個子串不同，當且僅當有這兩個子串長度不一樣或者長度一樣且有任意一位不一樣。

子串的定義：原字符串中連續(xù)的一段字符組成的字符串。

題解：

對于任何一個字串，一定是一個后綴的前綴，所以我們可以求出用后綴數(shù)組求出LCP（最長公共前綴），再求出每個后綴對答案的貢獻。
一個長度為n的字符串，產(chǎn)生的字符串的個數(shù)是n(n+1)/2個，這是總數(shù)
現(xiàn)在我們開始考慮重復(fù)的情況：

后綴sa[i-1]:aaabbdbs
后綴 sa[i]:aabbdbs

height[i]就是2，最前面兩個aa是都有的，是重復(fù)的，說明這個重復(fù)個數(shù)正好就是height[i]
但是后面重復(fù)情況(bbdbs部分是重復(fù))呀？但其實沒關(guān)系，因為我們處理了所有的后綴，總會有一個情況處理了bbdbs這情況。這樣我們求出整個串中重復(fù)的串的個數(shù)，就是${\sum }_{i=1}^{n}height[i]$
答案就是：n(n+1)/2-${\sum }_{i=1}^{n}height[i]$
記得開ll

代碼：

// Problem: P2408 不同子串個數(shù) // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P2408 // Memory Limit: 125 MB // Time Limit: 1000 ms // Data:2021-08-22 12:24:46 // By Jozky#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) {x= 0;char c= getchar();bool flag= 0;while (c < '0' || c > '9')flag|= (c == '-'), c= getchar();while (c >= '0' && c <= '9')x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();if (flag)x= -x;read(Ar...); } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test() { #ifdef LOCALstartTime= clock();freopen("in.txt", "r", stdin); #endif } void Time_test() { #ifdef LOCALendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int MAXN= 1000005;char ch[MAXN], all[MAXN]; int sa[MAXN], rk[MAXN], height[MAXN], tax[MAXN], tp[MAXN], a[MAXN], n, m; char str[MAXN]; //rk[i] 第i個后綴的排名; sa[i] 排名為i的后綴位置; height[i] 排名為i的后綴與排名為(i-1)的后綴的LCP //tax[i] 計數(shù)排序輔助數(shù)組; tp[i] rk的輔助數(shù)組(計數(shù)排序中的第二關(guān)鍵字),與sa意義一樣。 //a為原串 void RSort() {//rk第一關(guān)鍵字,tp第二關(guān)鍵字。for (int i= 0; i <= m; i++)tax[i]= 0;for (int i= 1; i <= n; i++)tax[rk[tp[i]]]++;for (int i= 1; i <= m; i++)tax[i]+= tax[i - 1];for (int i= n; i >= 1; i--)sa[tax[rk[tp[i]]]--]= tp[i]; //確保滿足第一關(guān)鍵字的同時，再滿足第二關(guān)鍵字的要求 } //計數(shù)排序,把新的二元組排序。int cmp(int* f, int x, int y, int w) {return f[x] == f[y] && f[x + w] == f[y + w]; } //通過二元組兩個下標的比較，確定兩個子串是否相同void Suffix() {//safor (int i= 1; i <= n; i++)rk[i]= a[i], tp[i]= i;m= 127, RSort(); //一開始是以單個字符為單位，所以(m = 127)for (int w= 1, p= 1, i; p < n; w+= w, m= p) { //把子串長度翻倍,更新rk//w 當前一個子串的長度; m 當前離散后的排名種類數(shù)//當前的tp(第二關(guān)鍵字)可直接由上一次的sa的得到for (p= 0, i= n - w + 1; i <= n; i++)tp[++p]= i; //長度越界,第二關(guān)鍵字為0for (i= 1; i <= n; i++)if (sa[i] > w)tp[++p]= sa[i] - w;//更新sa值,并用tp暫時存下上一輪的rk(用于cmp比較)RSort(), swap(rk, tp), rk[sa[1]]= p= 1;//用已經(jīng)完成的sa來更新與它互逆的rk,并離散rkfor (i= 2; i <= n; i++)rk[sa[i]]= cmp(tp, sa[i], sa[i - 1], w) ? p : ++p;}//離散：把相等的字符串的rk設(shè)為相同。//LCPint j, k= 0;for (int i= 1; i <= n; height[rk[i++]]= k)for (k= k ? k - 1 : k, j= sa[rk[i] - 1]; a[i + k] == a[j + k]; ++k);//這個知道原理后就比較好理解程序 }void Init() {int t;read(t);scanf("%s", str);// cout << str << endl;n= strlen(str);for (int i= 0; i < n; i++)a[i + 1]= str[i]; } int main() {//rd_test();Init();Suffix();ll ans= 0;// for (int i= 1; i <= n; i++)// cout << "hei[]=" << height[i] << endl;for (int i= 1; i <= n; i++) {ans+= 1ll * (n - i + 1) - 1ll * (height[sa[i]]);}cout << ans;// for (int i= 1; i <= n; i++) {// cout << "rank[i]=" << rk[i] << endl;// }// for (int i= 1; i <= n; i++) {// cout << "hei[i]=" << height[rk[i]] << endl;// }/*aabaaabaabaaaaaaaaaabaaabaabaa*///Time_test(); }

總結(jié)

以上是生活随笔為你收集整理的P2408 不同子串个数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。