题解 UVA12206 【Stammering Aliens】

终于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++;//相等加1
        else 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;
}