深圳福田网站设计,网站建设投标书模板,贡嘎网站建设,flashfxp上传多个网站题干#xff1a;
链接#xff1a;https://ac.nowcoder.com/acm/contest/551/C 来源#xff1a;牛客网
为了改变这一点#xff0c;他决定重新设定一个密码。于是他随机生成了一个很长很长的字符串#xff0c;并打算选择一个子串作为新密码。他认为安全的密码长度至少为…题干
链接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 等概率随机生成。 解题报告
llen-1n写成了那个上界了所以一直WA当时第一次设定的上界是200.不然知道T了就上界改小一点可能就A了。
这题因为数据随机所以变得异常简单考虑两个字符串在长度都为len的情况下完全相同的概率就是1/(26^len)在len比较大的时候就是个天文数字所以emmm随便找个上界做就行了。
by the way正解是后缀数组sa 或者 后缀自动机sam然而并不会
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#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;
setstring ss;
string tmp;
int n,m;
int main()
{int t;cinnm;cins;if(n15) {for(int len m; lenn; len) {for(int l 0; llen-1n; l) {tmp s.substr(l,len);ss.insert(tmp);}}cout ss.size()endl;}else {for(int len m; len8; len) {for(int l 0; llen-1n; l) {tmp s.substr(l,len);ss.insert(tmp);}}ll ans (ll)ss.size();for(int i max(9,m); in; i) {ans n-i1;}cout ans endl;}return 0 ;
}
