程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 3882（Stammering Aliens）後綴數組或者 hash

poj 3882（Stammering Aliens）後綴數組或者 hash

編輯：C++入門知識

poj 3882（Stammering Aliens）後綴數組或者 hash

後綴數組：構建後綴數組，注意要在字符串莫末尾加上一個沒出現過的字符。然後可以2分或者直接掃描，直接掃描需要用單調隊列來維護

VIEW CODE

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int mmax= 40010;
const int mod=1000000007;
typedef long long LL;
//typedef unsigned long long ULL;
char s[mmax];
int sa[mmax],t[mmax],t2[mmax],c[mmax],n;
void build_sa(int m)
{
    int i,*x=t,*y=t2;
    for(i=0;i=0;i--) sa[--c[x[i]]]=i;
    for(int k=1;k<=n;k<<=1)
    {
        int p=0;
        for(i=n-k;i=k) y[p++]=sa[i]-k;

        for(i=0;i=0;i--) sa[--c[x[y[i]]]]=y[i];
        swap(x,y);
        p=1;x[sa[0]]=0;
        for(i=1;i=n) break;
        m=p;
    }
}

int rank[mmax],heigth[mmax];
void getheigth()
{
    for(int i=0;ihead && heigth[len[end-1]]>= heigth[i])
                end--;
            len[end++]=i;
            while(end1>head1 && sa[mark[end1-1]] head && heigth[len[end-1]]>= heigth[i])
                end--;
            len[end++]=i;

            if(i-m==mark[head1])
                head1++;
            while(end1>head1 && sa[mark[end1-1]] ans)
            {
                ans=heigth[len[head]];
                e=sa[mark[head1]];
            }
            else if(heigth[len[head]]==ans)
                e=max(e,sa[mark[head1]]);
        }
        if(ans==0)
        {
            puts("none");
            continue;
        }
        printf("%d %d\n",ans,e);
    }
    return 0;
}

字符串hash ：直接2分了很好寫的

VIEW CODE

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int mmax= 1000010;
const int mod=1000000007;
const int inf=0x3fffffff;
using namespace std;
typedef long long  LL;
typedef unsigned long long ULL;
ULL H[mmax];


mapq;
int m;
char str[mmax];
ULL Pow[mmax];
void build_ha()
{
    int n=strlen(str);
    H[n]=0;
    for(int i=n-1;i>=0;i--)
        H[i]=H[i+1]*131+str[i];
}
ULL Ha[mmax];
bool ok(int k)
{
    int n=strlen(str);
    for(int i=0;i+k-1=m)
                return 1;
            cnt=1;
        }
    }
    if(cnt>=m)
        return 1;
    return 0;
}
int main()
{
    Pow[0]=1;
    for(int i=1;i>m&&m)
    {
        scanf("%s",str);
        int n=strlen(str);
        int l=1,r=n+1;
        build_ha();
        while(l>1;
            if(ok(mid))
                l=mid+1;
            else
                r=mid;
        }

        int ans=r-1;
        if(!ans)
        {
            puts("none");
            continue;
        }
        int e;
        q.clear();
        for(int i=0;i+ans-1=m)
                e=i;
        }
        printf("%d %d\n",ans,e);
    }
    return 0;
}