題解 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;
}