题干:
链接:https://ac.nowcoder.com/acm/contest/551/C
来源:牛客网
为了改变这一点,他决定重新设定一个密码。于是他随机生成了一个很长很长的字符串,并打算选择一个子串作为新密码。他认为安全的密码长度至少为 m,那么他有多少种不同选择方式呢?两种方案不同,当且仅当选出的密码内容不同。
输入描述:
第一行有两个整数 n 和 m ,分别表示 CSL 随机生成的字符串长度和安全的密码的最短长度。
第二行有一个长度为 n 的只含小写字母的字符串 s 表示 CSL 随机生成的字符串。
1≤m≤n≤1051≤m≤n≤105
输出描述:
在一行输出一个整数,表示 CSL 能选择的方案数。
示例1
输入
9 1 abcabcabc
输出
24
备注:
除样例外,所有的测试数据的字符串的每个字符均从小写字母 a - z 等概率随机生成。
解题报告:
l+len-1<n写成了<那个上界了,,所以一直WA,,当时第一次设定的上界是200.不然知道T了就上界改小一点可能就A了。
这题因为数据随机,所以变得异常简单,考虑两个字符串在长度都为len的情况下,完全相同的概率就是1/(26^len),在len比较大的时候就是个天文数字,所以emmm随便找个上界做就行了。
by the way,正解是后缀数组sa 或者 后缀自动机sam(然而并不会)
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 ;
}