终于A了这道题啊(坑啊)
教练说：这道题不能用map吧，复杂度不一个O(nlogn)吗
于是我就一直想不出来，然后看题解代码，一看就是map...
所以我就在想，那复杂度是不是也不是O(nlogn)呢
教练看了半天，说：好像确实不是诶
原来阻挡我的最大障碍是教练啊!!!(当时只给题面，也不知道时限)
看到这道题题面，找最长，位置又是有序的，肯定就能想到二分(然而我脑抽，想了几分钟才想到)
然后check里怎么写呢，这是最大的问题
能不能直接判断两者相不相等呢，我们可以使用字符串哈希!!!(这就不要讲了吧)
但是位置一个个枚举吗(时间空间双爆炸!!!)?
我们只能选择更优的办法，要是能把值相等的放在一起，符合的选最大位置就好了。
我想了很久，一开始使用map(被老师坑了)，后面突然想到一个好东西，sort!!!(然而又被老师坑了)
sort可以将几个值相等的放一起，但却不知道初始位置，不过这个一下就解决了，可以再用个数组记录嘛
于是就写了下来，然后惊奇地发现，过了!!!
代码如下(有几个坑点):
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int n,m,wz;char s[400004];unsigned long long p[400004],sum[400004];inline int max(int a,int b){return a>b?a:b;}struct ab{//结构体,a记值，b记位置unsigned long long a;int b;}t[400004];inline bool cmp(ab x,ab y){//快排，值相等位置大的放后面return x.a<y.a||(x.a==y.a&&x.b<y.b);}inline bool check(int x){wz=0;for(int i=1;i<=n-x+1;i++)t[i].a=sum[i+x-1]-sum[i-1]*p[x],t[i].b=i;sort(t+1,t+2+n-x,cmp);int j=1;//j开始要置1，因为开始就是一个for(int i=1;i<=n-x+1;i++){if(t[i].a==t[i-1].a)j++;//相等加1else j=1;if(j>=m)wz=max(wz,t[i].b);//可以就选大 }if(wz)return true;return false;}int main(){p[0]=1;for(int i=1;i<=400000;i++)p[i]=p[i-1]*131;scanf("%d",&m);while(m){int ans1=0,ans2=0;scanf("\n%s",s+1);n=strlen(s+1);for(int i=1;i<=n;i++)sum[i]=sum[i-1]*131+s[i];//字符串哈希int l=1,r=n;int ss=0;while(l<=r){//用l<=r,预防l==r的时候有解却没记录int mid=(l+r+1)/2;if(check(mid))ans1=mid,l=mid+1,ss++,ans2=wz-1;else r=mid-1;}if(!ss)printf("none\n");//没有找到符合的解else printf("%d %d\n",ans1,ans2);scanf("%d",&m);}return 0;}
