題干：

鏈接：https://ac.nowcoder.com/acm/contest/551/C
來(lái)源：牛客網(wǎng)
?

為了改變這一點(diǎn)，他決定重新設(shè)定一個(gè)密碼。于是他隨機(jī)生成了一個(gè)很長(zhǎng)很長(zhǎng)的字符串，并打算選擇一個(gè)子串作為新密碼。他認(rèn)為安全的密碼長(zhǎng)度至少為 m，那么他有多少種不同選擇方式呢？兩種方案不同，當(dāng)且僅當(dāng)選出的密碼內(nèi)容不同。

輸入描述:

第一行有兩個(gè)整數(shù) n 和 m ，分別表示 CSL 隨機(jī)生成的字符串長(zhǎng)度和安全的密碼的最短長(zhǎng)度。

第二行有一個(gè)長(zhǎng)度為 n 的只含小寫字母的字符串 s 表示 CSL 隨機(jī)生成的字符串。

?

1≤m≤n≤1051≤m≤n≤105

輸出描述:

在一行輸出一個(gè)整數(shù)，表示 CSL 能選擇的方案數(shù)。

示例1

輸入

復(fù)制

9 1 abcabcabc

輸出

復(fù)制

24

備注:

除樣例外，所有的測(cè)試數(shù)據(jù)的字符串的每個(gè)字符均從小寫字母 a - z 等概率隨機(jī)生成。

?

解題報(bào)告：

l+len-1<n寫成了<那個(gè)上界了，，所以一直WA，，當(dāng)時(shí)第一次設(shè)定的上界是200.不然知道T了就上界改小一點(diǎn)可能就A了。

這題因?yàn)閿?shù)據(jù)隨機(jī)，所以變得異常簡(jiǎn)單，考慮兩個(gè)字符串在長(zhǎng)度都為len的情況下，完全相同的概率就是1/(26^len)，在len比較大的時(shí)候就是個(gè)天文數(shù)字，所以emmm隨便找個(gè)上界做就行了。

by the way，正解是后綴數(shù)組sa 或者 后綴自動(dòng)機(jī)sam（然而并不會(huì)）

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; int pos[MAX]; char zz[MAX]; //char s[MAX]; string s; set<string> ss; string tmp; int n,m; int main() {int t;cin>>n>>m;cin>>s;if(n<=15) {for(int len = m; len<=n; len++) {for(int l = 0; l+len-1<n; l++) {tmp = s.substr(l,len);ss.insert(tmp);}}cout << ss.size()<<endl;}else {for(int len = m; len<=8; len++) {for(int l = 0; l+len-1<n; l++) {tmp = s.substr(l,len);ss.insert(tmp);}}ll ans = (ll)ss.size();for(int i = max(9,m); i<=n; i++) {ans += n-i+1;}cout << ans << endl;}return 0 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【牛客 - 551C】CSL 的密码（后缀数组，后缀自动机，随机算法）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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