99久久亚洲综合精品成人网 ,国产av一区二区不卡,国产99视频精品免费视频36

#include "stdio.h"
#define maxn 20000

int wa[maxn],wb[maxn],wv[maxn],ws[maxn];
int cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int *r,int *sa,int n,int m)
{
     int i,j,p,*x=wa,*y=wb,*t;
     for(i=0;i<m;i++) ws[i]=0;
     for(i=0;i<n;i++) ws[x[i]=r[i]]++;
     for(i=1;i<m;i++) ws[i]+=ws[i-1];
     for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
     for(j=1,p=1;p<n;j*=2,m=p)
     {
       for(p=0,i=n-j;i<n;i++) y[p++]=i;
       for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
       for(i=0;i<n;i++) wv[i]=x[y[i]];
       for(i=0;i<m;i++) ws[i]=0;
       for(i=0;i<n;i++) ws[wv[i]]++;
       for(i=1;i<m;i++) ws[i]+=ws[i-1];
       for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
       for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
       x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
     }
     return;
}
int rank[maxn],height[maxn];
void calheight(int *r,int *sa,int n)
{
     int i,j,k=0;
     for(i=1;i<=n;i++) rank[sa[i]]=i;
     for(i=0;i<n;height[rank[i++]]=k)
     for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
     return;
}

int check(int *sa,int n,int k)
{
    int i,max=sa[1],min=sa[1];//排在第一位的后綴的起始位置
    for(i=2;i<=n;i++)
    {
      if(height[i]<k) max=min=sa[i]; //分成heigh[i]<k的一組
      else //分成height[i]>=k的一組
      {
        if(sa[i]<min) min=sa[i];
        if(sa[i]>max) max=sa[i];
        if(max-min>k) return(1); //由于不可以重疊，所以兩個后綴的其實位置的差要大于k      
}
    }
    return(0);
}
int r[maxn],sa[maxn];
int main()
{
    int i,j=0,k,n;
    int min,mid,max;
    scanf("%d",&n);
    while(n!=0)
    {
      n--;
      scanf("%d",&j);
      for(i=0;i<n;i++)
      {
        scanf("%d",&k);
        r[i]=k-j+100;
        j=k;
      }
      r[n]=0;
      da(r,sa,n+1,200);
      calheight(r,sa,n);
      min=1;max=n/2;// 二分的數值范圍是1~n/2
      while(min<=max)
      {
        mid=(min+max)/2;
        if(check(sa,n,mid)) min=mid+1;
        else max=mid-1;
      }
      if(max>=4) printf("%d\n",max+1);
      else printf("0\n");
      scanf("%d",&n);
    }
    return 0;
}

2.可重疊k次的最長子串(至少重疊k次)

第二個懂了的后綴數組題目 poj 3261 題目http://poj.org/problem?id=3261

第二個懂了的后綴數組題目 poj 3261 源代碼如下：

View Code

#include<stdio.h>
#define maxn 20001
#define maxm 1000002

int wa[maxn],wb[maxn],wv[maxn],ws[maxm];
int cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int *r,int *sa,int n,int m)
{
     int i,j,p,*x=wa,*y=wb,*t;
     for(i=0;i<m;i++) ws[i]=0;
     for(i=0;i<n;i++) ws[x[i]=r[i]]++;
     for(i=1;i<m;i++) ws[i]+=ws[i-1];
     for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
     for(j=1,p=1;p<n;j*=2,m=p)
     {
       for(p=0,i=n-j;i<n;i++) y[p++]=i;
       for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
       for(i=0;i<n;i++) wv[i]=x[y[i]];
       for(i=0;i<m;i++) ws[i]=0;
       for(i=0;i<n;i++) ws[wv[i]]++;
       for(i=1;i<m;i++) ws[i]+=ws[i-1];
       for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
       for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
       x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
     }
     return;
}
int rank[maxn],height[maxn];
void calheight(int *r,int *sa,int n)
{
     int i,j,k=0;
     for(i=1;i<=n;i++) rank[sa[i]]=i;
     for(i=0;i<n;height[rank[i++]]=k)
     for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
     return;
}

int check(int n, int k, int mid)
{
    int i, Cnt = 1;//因為每找到一個height[i]就表示兩個后綴的比較結果，所以Cnt=1,不是Cnt=0
    for(i=2; i<=n; i++)
    {
        if(height[i]>=mid)//在同一組,累加
        {
            Cnt++;
            if(Cnt>=k) return 1;
        }
        else Cnt =1;//轉到了另外一組，那么要將Cnt值為1
    }
    return 0;
}
int r[maxn], sa[maxn];
int main()
{
    int i, j, k, n;
    int min, max, mid;
    while(scanf("%d%d", &n, &k)!=EOF)
    {
        for(i=0; i<n; i++)
        {
            scanf("%d", &r[i]);
            r[i]++;
        }
        r[n] = 0;
        da(r, sa, n+1, maxm);
        calheight(r, sa, n);
        min = 1; max = n;
        while(min<=max)
        {
            mid = (mid+max)/2;
            if(check(n, k, mid)) min = mid+1;
            else max = mid-1;
        }
        printf("%d\n", max);
    }
    return 0;
}

3.不相同的子串個數

第三個懂了的后綴數組題目 spoj 694 題目http://www.spoj.pl/problems/DISUBSTR/

第三個懂了的后綴數組題目 spoj 694 源代碼如下：

View Code

#include "stdio.h"
#include "string.h"
#define maxn 50001

int wa[maxn],wb[maxn],wv[maxn],ws[maxn];
int cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int *r,int *sa,int n,int m)
{
     int i,j,p,*x=wa,*y=wb,*t;
     for(i=0;i<m;i++) ws[i]=0;
     for(i=0;i<n;i++) ws[x[i]=r[i]]++;
     for(i=1;i<m;i++) ws[i]+=ws[i-1];
     for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
     for(j=1,p=1;p<n;j*=2,m=p)
     {
       for(p=0,i=n-j;i<n;i++) y[p++]=i;
       for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
       for(i=0;i<n;i++) wv[i]=x[y[i]];
       for(i=0;i<m;i++) ws[i]=0;
       for(i=0;i<n;i++) ws[wv[i]]++;
       for(i=1;i<m;i++) ws[i]+=ws[i-1];
       for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
       for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
       x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
     }
     return;
}
int rank[maxn],height[maxn];
void calheight(int *r,int *sa,int n)
{
     int i,j,k=0;
     for(i=1;i<=n;i++) rank[sa[i]]=i;
     for(i=0;i<n;height[rank[i++]]=k)
     for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
     return;
}

char s[maxn];
int r[maxn],sa[maxn];
int main()
{
    int i,n,t;
    long long ans;
    scanf("%d",&t);
    while(t-->0)
    {
      scanf("%s",s);
      n=strlen(s);
      for(i=0;i<n;i++) r[i]=s[i];
      r[n]=0;
      da(r,sa,n+1,128);
      calheight(r,sa,n);
      ans=(long long)n*(n+1)/2;
      for(i=1;i<=n;i++) ans-=height[i];
      printf("%lld\n",ans);
    }
    return 0;
}

4.最長回文子串

(求兩個后綴的最長公共前綴：就是求height[]中這兩個后綴區間的最小值)

第四個懂了的后綴數組題目 ural 1297 題目http://acm.timus.ru/problem.aspx?space=1&num=1297

第四個懂了的后綴數組題目 ural 1297 源代碼如下：

View Code

#include "stdio.h"
#include "string.h"
#include "math.h"
#define maxn 2002

int wa[maxn],wb[maxn],wv[maxn],ws[maxn];
int cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int *r,int *sa,int n,int m)
{
     int i,j,p,*x=wa,*y=wb,*t;
     for(i=0;i<m;i++) ws[i]=0;
     for(i=0;i<n;i++) ws[x[i]=r[i]]++;
     for(i=1;i<m;i++) ws[i]+=ws[i-1];
     for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
     for(j=1,p=1;p<n;j*=2,m=p)
     {
       for(p=0,i=n-j;i<n;i++) y[p++]=i;
       for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
       for(i=0;i<n;i++) wv[i]=x[y[i]];
       for(i=0;i<m;i++) ws[i]=0;
       for(i=0;i<n;i++) ws[wv[i]]++;
       for(i=1;i<m;i++) ws[i]+=ws[i-1];
       for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
       for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
       x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
     }
     return;
}
int rank[maxn],height[maxn];
void calheight(int *r,int *sa,int n)
{
     int i,j,k=0;
     for(i=1;i<=n;i++) rank[sa[i]]=i;
     for(i=0;i<n;height[rank[i++]]=k)
     for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
     return;
}
int RMQ[maxn];
int best[maxn][20];
void initRMQ(int n)
{
     int i,j,a,b;
     int l=int(log(double(n))/log(2.0));
     for(i=1;i<=n;i++) best[i][0]=i;
     for(i=1;i<=l;i++)
     for(j=1;j<=n+1-(1<<i);j++)
     {
       a=best[j][i-1];
       b=best[j+(1<<(i-1))][i-1];
       if(RMQ[a]<RMQ[b]) best[j][i]=a;//height[]值較小的才是最長公共前綴，但是記錄的是排序后的位置
       else best[j][i]=b;
     }
     return;
}
int askRMQ(int a,int b)
{
    int t=int(log(double(b-a+1))/log(2.0));
    a=best[a][t];b=best[b-(1<<t)+1][t];
    return RMQ[a]<RMQ[b]?a:b;//返回a，b這個區間段的最長公共前綴在排序中的位置
}
int lcp(int a,int b)//獲得最長公共前綴的長度
{
    int t;
    a=rank[a];b=rank[b];//分別獲得后綴su[a], su[b]在排序中的位置
    if(a>b) {t=a;a=b;b=t;}
    return(height[askRMQ(a+1,b)]);//得到最長公共前綴的長度
}

char st[maxn];
int r[maxn],sa[maxn];
int main()
{
    int i,n,len,k,ans=0,w;
    scanf("%s",st);
    len=strlen(st);
    for(i=0;i<len;i++) r[i]=st[i];
    r[len]=1;
    for(i=0;i<len;i++) r[i+len+1]=st[len-1-i];
    n=len+len+1;
    r[n]=0;
    da(r,sa,n+1,128);
    calheight(r,sa,n);
    for(i=1;i<=n;i++) RMQ[i]=height[i];
    initRMQ(n);
    for(i=0;i<len;i++)
    {
      k=lcp(i,n-i);//奇數或偶數
      if(k*2>ans) ans=k*2,w=i-k; //ans保存最長公共前綴的結果，w保存最長公共前綴在字符串的其實位置

      k=lcp(i,n-i-1);//偶數或奇數
      if(k*2-1>ans) ans=k*2-1,w=i-k+1;
    }
    st[w+ans]=0;
    printf("%s\n",st+w);
    return 0;
}

5.連續重復子串

第五個懂了的后綴數組題目 poj 2406 題目http://poj.org/problem?id=2406

第五個懂了的后綴數組題目 poj 2406 源代碼如下：（超時，沒辦法這個題目卡的就是后綴數組，TMD）

View Code

#include "math.h"
#include<stdio.h>
#include<string.h>
#define maxn 1000005
#define maxm 300
char s[maxn];
int r[maxn], sa[maxn];
int wa[maxn],wb[maxn],wv[maxn],ws[maxn];
int cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int *r,int *sa,int n,int m)
{
     int i,j,p,*x=wa,*y=wb,*t;
     for(i=0;i<m;i++) ws[i]=0;
     for(i=0;i<n;i++) ws[x[i]=r[i]]++;
     for(i=1;i<m;i++) ws[i]+=ws[i-1];
     for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
     for(j=1,p=1;p<n;j*=2,m=p)
     {
       for(p=0,i=n-j;i<n;i++) y[p++]=i;
       for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
       for(i=0;i<n;i++) wv[i]=x[y[i]];
       for(i=0;i<m;i++) ws[i]=0;
       for(i=0;i<n;i++) ws[wv[i]]++;
       for(i=1;i<m;i++) ws[i]+=ws[i-1];
       for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
       for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
       x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
     }
     return;
}
int rank[maxn],height[maxn];
void calheight(int *r,int *sa,int n)
{
     int i,j,k=0;
     for(i=1;i<=n;i++) rank[sa[i]]=i;
     for(i=0;i<n;height[rank[i++]]=k)
     for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
     return;
}
int RMQ[maxn];
int best[maxn][20];
void initRMQ(int n)
{
     int i,j,a,b;
     int l=int(log(double(n))/log(2.0));
     for(i=1;i<=n;i++) best[i][0]=i;
     for(i=1;i<=l;i++)
     for(j=1;j<=n+1-(1<<i);j++)
     {
       a=best[j][i-1];
       b=best[j+(1<<(i-1))][i-1];
       if(RMQ[a]<RMQ[b]) best[j][i]=a;//height[]值較小的才是最長公共前綴，但是記錄的是排序后的位置
       else best[j][i]=b;
     }
     return;
}
int askRMQ(int a,int b)
{
    int t=int(log(double(b-a+1))/log(2.0));
    a=best[a][t];b=best[b-(1<<t)+1][t];
    return RMQ[a]<RMQ[b]?a:b;//返回a，b這個區間段的最長公共前綴在排序中的位置
}
int lcp(int a,int b)//獲得最長公共前綴的長度
{
    int t;
    a=rank[a];b=rank[b];//分別獲得后綴su[a], su[b]在排序中的位置
    if(a>b) {t=a;a=b;b=t;}
    return(height[askRMQ(a+1,b)]);//得到最長公共前綴的長度
}
void getans(int n)
{
    int i, ans;
    for(i=n;i>0; i--)
    {
        
        if(n%i==0 && lcp(0, i)==n-i) ans=n/i;
    }
    printf("%d\n", ans);
}

int main()
{
    int i, n, t;
    while(~scanf("%s", s))
    {
        if(strcmp(s, ".")==0) break;
        n=strlen(s);
        for(i=0; i<n; i++) r[i]=s[i];
        r[n]=0;
        da(r, sa, n+1, 300);
        calheight(r, sa, n);
        for(i=1;i<=n;i++) RMQ[i]=height[i];
        initRMQ(n);
        getans(n);
    }
    return 0;
}

5.KMP問題

kmp算法詳解：http://bbezxcy.iteye.com/blog/1355293

基礎kmp題目 poj 3461 http://poj.org/problem?id=3461

poj 3461 源代碼如下

View Code

#include "iostream"
#include "string"
#include "algorithm"
using namespace std;
char a[1000010], b[10010];
int p[11111];
int n, m;
void getp()
{
    p[1] = 0;
    int i, j=0;
    for(i=2; i<=m; i++)
    {
        while(j>0 && b[j+1]!=b[i]) j=p[j];
        if(b[j+1]==b[i]) j+=1;
        p[i]=j;
    }
}
void kmp()
{
    int i, j=0, cnt=0;
    for(i=1; i<=n; i++)
    {
        while(j>0 && b[j+1]!=a[i]) j=p[j];//不相等時，j往前返回
        if(b[j+1]==a[i]) j+=1; //相等時j加1
        if(j==m)
        {
            cnt++;
            j=p[j]; //j返回，重新再來匹配
        }
    }
    printf("%d\n", cnt);
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>(b+1)>>(a+1);
        m=strlen(b+1);
        n=strlen(a+1);
        getp();
        kmp();
    }
}

kmp理解型題目 poj 2406 http://poj.org/problem?id=2406

poj 2406 源代碼如下

View Code

#include "iostream"
#include "string"
#include "algorithm"
using namespace std;
char b[1000010];
int p[1000010];
int m;
void getp()
{
    p[1] = 0;
    int i, j=0;
    for(i=2; i<=m; i++)
    {
        while(j>0 && b[j+1]!=b[i]) j=p[j];
        if(b[j+1]==b[i]) j+=1;
        p[i]=j;
    }
}
int main()
{
    while(cin>>(b+1))
    {        
        if(strcmp(b+1,".")==0) break;
        m=strlen(b+1);
        getp();
        if(0==m%(m-p[m])) printf("%d\n", m/(m-p[m]));
        else printf("1\n");
    }
}

posted on 2012-08-05 09:35 More study needed. 閱讀(283) 評論(1) 收藏舉報

刷新頁面返回頂部

磚提1

導航

公告