标签存档：字符串

题意：

题目：https://www.spoj.pl/problems/PHRASES/

给定N个字符串，让你求一个最长的串，使得他满足：

在每个串中它都出现过>=两次，而且出现的位置不重叠。

分析：

就是构造后缀数组，然后二分答案，用分组思想，看能否实现。

HINT

一开始没看到不能重叠，WA了一遍。

code：

#include #include #include using namespace std;
const int N=111111;
char s[N];
struct gtp{int data[3],next;}g[N];
int cn,ls[N],color[N],e,n,sa[N],rank[N],a[N][3],G[N],hash[N],num[N],height[N],maxsa[N],minsa[N],list[N];

void init(){
     char inschar=’A’,ch;
     scanf("%dn",&cn);
     n=0;
     for (int i=1;i<=cn;i++){
         while (scanf("%c",&ch)!=EOF && ch!=’n’)
           if (ch>=’a’ && ch<='z'){
             s[++n]=ch;
             color[n]=i;
           }
         s[++n]=inschar++;
         color[n]=0;
     }
}

inline bool cmp(int x,int y){
     if (s[x]     return false;
}

inline void add(int x,int data[]){
       e++;
       g[e].next=ls[x]; ls[x]=e;
       memcpy(g[e].data,data,sizeof(a[0]));
}

void Jsort(){
     for (int k=1;k>=0;k–){
         e=0;
         memset(ls,0,sizeof(int)*(n+1));
         for (int i=n;i>=1;i–) add(a[i][k],a[i]);
         int tail=0;
         for (int i=0;i<=n;i++)
           for (int t=ls[i];t!=0;t=g[t].next)
             memcpy(a[++tail],g[t].data,sizeof(a[0]));
     }
}

void buildarr(){
     for (int i=1;i<=n;i++) sa[i]=i;
     sort(&sa[1],&sa[n+1],cmp);
     int tail=0;
     for (int i=1;i<=n;i++){
         if (i==1 || s[sa[i]]!=s[sa[i-1]]) tail++;
         rank[sa[i]]=tail;
     }
     for (int k=1;1<         int t=1<         for (int i=1;i<=n;i++){
             a[i][0]=rank[i];
             if (i+t<=n) a[i][1]=rank[i+t];
                    else a[i][1]=0;
             a[i][2]=i;
         }
         Jsort();
         tail=0;
         for (int i=1;i<=n;i++){
             if (i==1 || a[i][0]!=a[i-1][0] || a[i][1]!=a[i-1][1]) tail++;
             rank[a[i][2]]=tail;
         }
     }
     for (int i=1;i<=n;i++) sa[rank[i]]=i;
}

void MakeHeight(){
     memset(height,0,sizeof(int)*(n+1));
     for (int i=1;i<=n;i++){
         if (rank[i]==1) continue;
         int st=max(height[rank[i-1]]-1,0),j=i+st,k=sa[rank[i]-1]+st;
         while (j<=n && k<=n && s[j]==s[k]) {j++;k++;st++;}
         height[rank[i]]=st;
     }
}

bool flag(int limit){
     int Gn=1; G[1]=1;
     for (int i=2;i<=n;i++)
       if (height[i]>=limit) G[i]=Gn;
                        else G[i]=++Gn;
     int j=1;
     for (int i=1;i<=Gn;i++){
         int st=j,total=0,tail=0;
         while (j<=n && G[j]==i) j++;
         for (int k=st;k           if (hash[color[sa[k]]]!=i){
             hash[color[sa[k]]]=i;
             num[color[sa[k]]]=1;
             minsa[color[sa[k]]]=sa[k];
             maxsa[color[sa[k]]]=sa[k];
             list[++tail]=color[sa[k]];
           }
           else{
             num[color[sa[k]]]++;
             minsa[color[sa[k]]]=min(minsa[color[sa[k]]],sa[k]);
             maxsa[color[sa[k]]]=max(maxsa[color[sa[k]]],sa[k]);
             if (num[color[sa[k]]]==2 && color[sa[k]]!=0) total++;
           }
         if (total!=cn) continue;
         bool ff=true;
         for (int k=1;k<=tail;k++)
           if (maxsa[k]-minsa[k]         if (ff) return true;
     }
     return false;
}

void binary(){
     int l=0,r=n,mid;
     while (l+1           mid=l+r>>1;
           if (flag(mid)) l=mid;
                     else r=mid-1;
     }
     if (flag(r)) printf("%dn",r);
             else printf("%dn",l);
}

int main(){
    int testcase;
    scanf("%d",&testcase);
    for (int i=1;i<=testcase;i++){
        init();
        buildarr();
        MakeHeight();
        binary();
    }
}

题意：

给出一个串，求这个串的最长的出现过至少k次的子串。出现的位置可以重叠。

分析：

用后缀数组先处理出height数组，然后二分答案，根据limit将height分组，使得每一组里任意串的lcp>=limit。

然后如果某一组的串的个数超过>=k，那么flag=true。

插曲：

基数排序时e没有设为0，WA了和RE了好多遍。

code：

#include

题意：

楼教主男人8题里的一题。

给出一串数，让你找出最长的两段不重合的连续差值相等的子串。

分析：

先令S[I]=A[I]-A[I-1]，然后问题转化为求S[I]的最长不重合重复子串。

先用后缀数组处理好S[I]，然后二分答案分组，如果某一组里的MAX(SA[I])-MIN(SA[J])>LIMIT，表示这组可以找到不重合的答案。

然后输出即可。

插曲：

有一个地方Gn打成n了。WA了N久。

code：

#include #include #define max(x,y) (x)>(y)?(x):(y)
#define min(x,y) (x)<(y)?(x):(y)
const int N=22222;
struct gtp{int x,data[3],next;}g[N];
int n,s[N],sa[N],rank[N],height[N],a[N][3],ls[N],e;
int G[N],pu[20][N],pd[20][N],tmp[N],lg[N];

void init(){
    for (int i=0;i    for (int i=1;i    n–;
    int t=0; lg[1]=0;
    for (int i=1;i<=n;i++)
      if (1<                else lg[i]=lg[i-1];
}

inline void add(int x,int data[]){
    e++;
    g[e].x=x; g[e].next=ls[x]; ls[x]=e;
    memcpy(g[e].data,data,sizeof(a[0]));
}

void Jsort(){
    for (int k=1;k>=0;k–){
        e=0;
        for (int i=0;i<=n;i++) ls[i]=0;
        for (int i=n;i>=1;i–) add(a[i][k],a[i]);
        int tail=0;
        for (int i=0;i<=n;i++)
          for (int t=ls[i];t!=0;t=g[t].next)
              memcpy(a[++tail],g[t].data,sizeof(a[0]));
    }
}

void Sort(int l,int r){
    if (l>=r) return;
    int i=l,j=r,mid=s[sa[l+r>>1]],temp;
    while (i        while (s[sa[i]]        while (s[sa[j]]>mid) j–;
        if (i<=j){
            temp=sa[i]; sa[i]=sa[j]; sa[j]=temp;
            i++; j–;
        }
    }
    Sort(l,j);
    Sort(i,r);
}

void build(){
    for (int i=1;i<=n;i++) sa[i]=i;
    Sort(1,n);
    int tail=0;
    for (int i=1;i<=n;i++){
        if (i==1 || s[sa[i]]!=s[sa[i-1]]) tail++;
        rank[sa[i]]=tail;
    }
    for (int k=1;1<        for (int i=1;i<=n;i++){
            a[i][0]=rank[i];
            if (i+(1<                          else a[i][1]=0;
            a[i][2]=i;
        }
        Jsort();
        tail=0;
        for (int i=1;i<=n;i++){
            if (i==1 || a[i][0]!=a[i-1][0] || a[i][1]!=a[i-1][1]) tail++;
            rank[a[i][2]]=tail;
        }
    }
    for (int i=1;i<=n;i++) sa[rank[i]]=i;
}

void Sparse_Table(){
    for (int i=1;i<=n;i++) pu[0][i]=sa[i];
    for (int i=1;i<=n;i++) pd[0][i]=sa[i];
    for (int k=1;1<      for (int i=1;i+(1<        pu[k][i]=max(pu[k-1][i],pu[k-1][i+(1<        pd[k][i]=min(pd[k-1][i],pd[k-1][i+(1<      }
}

inline int Maxsa(int l,int r){
    int t=lg[r-l+1];
    return max(pu[t][l],pu[t][r-(1<}

inline int Minsa(int l,int r){
    int t=lg[r-l+1];
    return min(pd[t][l],pd[t][r-(1<}

void MakeHeight(){
    for (int i=0;i<=n;i++) height[i]=0;
    for (int i=1;i<=n;i++){
        if (rank[i]==1) continue;
        int st=max(height[rank[i-1]]-1,0),j=i+st,k=sa[rank[i]-1]+st;
        while (j<=n && k<=n && s[j]==s[k]){st++;j++;k++;}
        height[rank[i]]=st;
    }
}

bool flag(int limit){
    int Gn=1; G[1]=1;
    for (int i=2;i<=n;i++)
      if (height[i]>=limit) G[i]=Gn;
                       else G[i]=++Gn;
    int j=1;
    for (int i=1;i<=Gn;i++){
        int st=j;
        while (j<=n && G[j]==i) j++;
        int ed=j-1;
        if (Maxsa(st,ed)-Minsa(st,ed)>limit) return true;
    }
    return false;
}

int binary(){
    int l=0,r=n,mid;
    while (l+1        mid=l+r>>1;
        if (flag(mid)) l=mid;
                  else r=mid-1;
    }
    if (flag(r)) return r;
    return l;
}

int main(){
    while (scanf("%d",&n) && n!=0){
        init();
        build();
        Sparse_Table();
        MakeHeight();
        int ans=binary();
        if (ans<4) printf("0n");
              else printf("%dn",ans+1);
    }
}

题意：

找出最长的串，使其是在给定的N个串中，超过N/2个得子串。

如果有多个最长的串，那么按字典序输出所有的串。

分析：

先把所有串串起来，期间用不同的特殊字符间隔。

这里是为了保证后缀数组不会隔着组弄成lcp。

这题可以先用后缀数组处理出height数组。

然后二分答案（长度）。

Next，按顺序将height分组（每组是连续的），使得每一组里除了第一以外的height值都>=limit

如果里面有一组包含超过N/2个所归属的串，那么flag=true

如果flag=true，那么放大答案，否则减小。

最后按顺序取来输出就行了。

插曲：

1A

这次后缀数组部分短了大概50行= =，但还是比较长。

code：

#include #include #include using namespace std;
const int N=200000;
struct gtp{int x,data[3],next;}g[N];
char s[N],ts[N];
int n,sa[N],rank[N],height[N],len,v[N],a[N][3],ls[N],e,G[N];
int mark[N];

void init(){
    memset(s,0,sizeof(s));
    memset(v,0,sizeof(v));
    memset(sa,0,sizeof(sa));
    memset(rank,0,sizeof(rank));
    memset(height,0,sizeof(height));
    len=0;
    char tmp=’A’;
    for (int i=1;i<=n;i++){
        scanf("%s",&ts);
        int tlen=strlen(ts);
        for (int j=0;j          s[++len]=ts[j];
          v[len]=i;
        }
        s[++len]=tmp;
        tmp++;
        if (tmp>’Z’) tmp=’A’;
    }
}

void Sort(int l,int r){
    if (l>=r) return;
    int i=l,j=r; char mid=s[sa[l+r>>1]];
    while (i        while (s[sa[i]]        while (s[sa[j]]>mid) j–;
        if (i<=j){
            swap(sa[i],sa[j]);
            i++; j–;
        }
    }
    Sort(l,j);
    Sort(i,r);
}

inline void add(int x,int data[]){
    e++;
    g[e].x=x; g[e].next=ls[x]; ls[x]=e;
    memcpy(g[e].data,data,sizeof(a[0]));
}

void Jsort(){
    for (int k=1;k>=0;k–){
        e=0;
        memset(ls,0,sizeof(int)*(len+1));
        for (int i=len;i>=1;i–) add(a[i][k],a[i]);
        int tail=0;
        for (int i=0;i<=len;i++)
          for (int t=ls[i];t!=0;t=g[t].next)
            memcpy(a[++tail],g[t].data,sizeof(a[0]));
    }
}

void buildarr(){
    for (int i=1;i<=len;i++) sa[i]=i;
    Sort(1,len);
    int tail=0;
    for (int i=1;i<=len;i++){
        if (i==1 || s[sa[i]]!=s[sa[i-1]]) tail++;
        rank[sa[i]]=tail;
    }
    for (int k=2;k<=len;k<<=1){
        for (int i=1;i<=len;i++){
            a[i][0]=rank[i];
            if (i+(k>>1)<=len) a[i][1]=rank[i+(k>>1)];
                          else a[i][1]=0;
            a[i][2]=i;
        }
        Jsort();
        tail=0;
        for (int i=1;i<=len;i++){
            if (i==1 || a[i][0]!=a[i-1][0] || a[i][1]!=a[i-1][1]) tail++;
            rank[a[i][2]]=tail;
        }
    }
    for (int i=1;i<=len;i++) sa[rank[i]]=i;
}

void GetHeight(){
    for (int i=1;i<=len;i++){
        if (rank[i]==1) continue;
        int st=max(0,height[rank[i-1]]-1),j=i+st,k=sa[rank[i]-1]+st;
        while (j<=len && k<=len && s[j]==s[k]){st++; j++; k++;}
        height[rank[i]]=st;
    }
}

bool flag(int limit){
    bool ret=false;
    int Gn=1; G[1]=1;
    for (int i=2;i<=len;i++)
      if (height[i]>=limit) G[i]=Gn;
                       else G[i]=++Gn;
    memset(mark,0,sizeof(int)*(len+1));
    int j=1,num;
    for (int i=1;i<=Gn;i++){
        num=0;
        while (j<=len && G[j]==i) {
            if (v[sa[j]]!=0 && mark[v[sa[j]]]!=i){
                mark[v[sa[j]]]=i;
                num++;
            }
            j++;
        }
        if (num>n/2) ret=true;
    }
    return ret;
}

int binary(){
    int l=0,r=len,mid;
    while (l+1        mid=l+r>>1;
        if (flag(mid)) l=mid;
                  else r=mid-1;
    }
    if (flag(r)) return r;
    return l;
}

void print(int ans){
    if (ans==0) printf("?n");
    else{
        int Gn=1; G[1]=1;
        for (int i=2;i<=len;i++)
          if (height[i]>=ans) G[i]=Gn;
                         else G[i]=++Gn;
        memset(mark,0,sizeof(int)*(len+1));
        int j=1,num,st;
        for (int i=1;i<=Gn;i++){
          num=0;
          st=j;
          while (j<=len && G[j]==i) {
              if (v[sa[j]]!=0 && mark[v[sa[j]]]!=i){
                  mark[v[sa[j]]]=i;
                  num++;
              }
              j++;
          }
          if (num>n/2){
              for (int k=0;k                printf("%c",s[sa[st]+k]);
              printf("n");
          }
        }
    }
}

int main(){
    scanf("%dn",&n);
    while (n!=0){
        init();
        buildarr();
        GetHeight();
        int ans=binary();
        print(ans);
        scanf("%dn",&n);
        if (n!=0) printf("n");
    }
    return 0;
}

题意：

给定a串和b串，求他们的最长公共子串

分析：

把两个串连在一起。构造后缀数组。然后在构造等同于lcp(i-1,i)的height数组。

然后如果相邻的两个后缀分别属于a串和b串，那么就可以做答案。

时间复杂度O(nlgn)

1A

PS:第一次写后缀数组，写得有点繁杂，写多了，就会缩短了。。。

code:

#include #include #include #include #define N 300000
using namespace std;
char s[N],s1[N],s2[N];
struct gtp{int x,data[3],next;}g[N];
int n,len1,len2,sa[N],rank[N],a[N][3],e,ls[N],height[N];

void init(){
     scanf("%s",&s1);
     scanf("%s",&s2);
     len1=strlen(s1);
     len2=strlen(s2);
     n=0;
     for (int i=0;i         n++;
         s[n]=s1[i];
     }
     for (int i=0;i         n++;
         s[n]=s2[i];
     }
     s[0]=7;
}

void Sort(int l,int r){
     if (l>=r) return;
     int i=l,j=r;
     char mid=s[sa[(l+r)/2]];
     do{
          while (s[sa[i]]          while (s[sa[j]]>mid) j–;
          if (i<=j){
            swap(sa[i],sa[j]);
            i++; j–;
          }
     }while (i     Sort(l,j);
     Sort(i,r);
}

inline void add(int x,int data[]){
       e++;
       g[e].x=x;
       memcpy(g[e].data,data,sizeof(a[0]));
       g[e].next=ls[x];
       ls[x]=e;
}

void Jsort(){
     e=0;
     memset(ls,0,sizeof(int)*(n+2));
     for (int i=1;i<=n;i++)
       add(a[i][1],a[i]);
     int tail=0;
     for (int i=0;i<=n;i++){
         for (int t=ls[i];t!=0;t=g[t].next){
             tail++;
             memcpy(a[tail],g[t].data,sizeof(a[0]));
         }
     }

     e=0;
     memset(ls,0,sizeof(int)*(n+2));
     for (int i=n;i>=1;i–)
       add(a[i][0],a[i]);
     tail=0;
     for (int i=0;i<=n;i++)
       for (int t=ls[i];t!=0;t=g[t].next){
           tail++;
           memcpy(a[tail],g[t].data,sizeof(a[0]));
       }
}

inline bool flag(int d1[],int d2[]){
       if (d1[0]!=d2[0] || d1[1]!=d2[1]) return true;
       return false;
}

void buildarr(){
     for (int i=1;i<=n;i++) sa[i]=i;
     Sort(1,n);
     int t=0;
     for (int i=1;i<=n;i++){
       if (t==0 || s[sa[i]]!=s[sa[i-1]]) t++;
       rank[sa[i]]=t;
     }
     for (int i=1;1<         for (int j=1;j<=n;j++){
             a[j][0]=rank[j];
             if (j+(1<                          else a[j][1]=rank[j+(1<             a[j][2]=j;
         }
         Jsort();
         int t=0;
         for (int j=1;j<=n;j++){
             if (t==0 || flag(a[j],a[j-1])) t++;
             rank[a[j][2]]=t;
         }
     }
     for (int i=1;i<=n;i++) sa[rank[i]]=i;
}

void lcp(){
     memset(height,0,sizeof(height));
     for (int i=1;i<=n;i++){
         if (rank[i]==1) continue;
         int st,j,k;
         st=max(height[rank[i-1]]-1,0);
         j=i+st;
         k=sa[rank[i]-1]+st;
         while (j<=n && k<=n && s[j]==s[k]){
               st++;
               j++;
               k++;
         }
         height[rank[i]]=st;
     }
}

inline bool part(int k){
            if (k<=len1) return true;
            return false;
       }

void print(){
     int ans=0;
     for (int i=2;i<=n;i++)
       if (part(sa[i-1])^part(sa[i])) ans=max(ans,height[i]);
     cout << ans << endl;
}

int main(){
    init();
    buildarr();
    lcp();
    print();
}