题目描述

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

CSL的密码

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

输入描述:

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

1≤m≤n≤100000

输出描述:

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

输入

9 1
abcabcabc

输出

备注:

除样例外，所有的测试数据的字符串的每个字符均从小写字母 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;
}