链接：/acm/contest/551/C

来源：牛客网

时间限制：C/C++ 2秒，其他语言4秒

空间限制：C/C++ 524288K，其他语言1048576K

64bit IO Format: %lld

题目描述

众所周知，CSL 最喜欢的密码是 ******。于是有一天……

为了改变这一点，他决定重新设定一个密码。于是他随机生成了一个很长很长的字符串，并打算选择一个子串作为新密码。他认为安全的密码长度至少为 m，那么他有多少种不同选择方式呢？两种方案不同，当且仅当选出的密码内容不同。

输入描述:

第一行有两个整数 n 和 m ，分别表示 CSL随机生成的字符串长度和安全的密码的最短长度。

第二行有一个长度为 n 的只含小写字母的字符串 s 表示 CSL随机生成的字符串。

1≤m≤n≤100000

输出描述:

在一行输出一个整数，表示 CSL 能选择的方案数。

输入

9 1abcabcabc

输出

24

备注:

除样例外，所有的测试数据的字符串的每个字符均从小写字母 a - z 等概率随机生成。

思路：

比赛时没有做出来，赛后看别人的代码，发现有点投机取巧的意思

题目大意是让你找长度大于m的字符串有多少不同的，一般思路是直接暴力，把所有的长度大于m的字串全部找出来放入set中，输出下size就可以了，但是这样的话会T，那么你就认为如果字串的长度是大于某一个值得话，是不存在和它相同的字串的，所以直接一趟循环就求出来了，这个值的话15就可以

之所以能这么做，可能是因为那个备注

除样例外，所有的测试数据的字符串的每个字符均从小写字母 a - z 等概率随机生成。

随机生成

#include <iostream>#include <algorithm>#include <string>#include <cstring>#include <set>using namespace std;int main(){int n,m;long long ans=0;string a;cin>>n>>m;cin>>a;//如果长度小于15,需要判断是否重复for(int i=m;i<=min(15,n);i++) //字符串长度{set<string> st;for(int j=0;j<=n-i;j++) //字符串起点{string t=a.substr(j,i);st.insert(t);}ans+=st.size();} //长度大于15，就不需要判断了for(int i=max(16,m);i<=n;i++){ans+=n-i+1;}cout<<ans<<endl;return 0;}

如果觉得《CSL的密码》对你有帮助，请点赞、收藏，并留下你的观点哦！