DZY 's BLOG

拿SAM来求字符串的最小表示很煞笔吧、好吧、只是拿来练习SAM用的、

把字符串自复制一遍、然后建SAM、然后从root开始跑，每次都跑最小编号的结点，在上面跑|S|个结点。然后输出当前结点的信息就行了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct SAMNode{
    int ch[26],fa,len;
    inline void init(){
        fa=-1; len=0; memset(ch,0xff,sizeof(ch));
    }
}T[50010];
char s[10010];
int tot,last; 
void add(int c){
    int end=++tot; T[end].init();
    int tmp=last;
    T[end].len=T[last].len+1;
    while(tmp!=-1 && T[tmp].ch[c]==-1){
        T[tmp].ch[c]=end;
        tmp=T[tmp].fa;
    }if(!~tmp) T[end].fa=0;
    else{
        int next=T[tmp].ch[c];
        if(T[tmp].len+1==T[next].len) T[end].fa=next;
        else{
            int np=++tot; T[np].init();
            T[np]=T[next];
            T[np].len=T[tmp].len+1;
            T[end].fa=T[next].fa=np;
            while(tmp!=-1 && T[tmp].ch[c]==next){
                T[tmp].ch[c]=np;
                tmp=T[tmp].fa;
            }
        }
    }last=end;
}int main(){
    int tc;
    scanf("%d",&tc);
    while(tc--){
        tot=0; last=0; T[0].init();
        scanf("%s",s);
        int n=strlen(s);
        for(int i=0;i<n;i++) add(s[i]-'a');
        for(int i=0;i<n;i++) add(s[i]-'a');
        int o=0;
        for(int i=0;i<n;i++) for(int j=0;j<26;j++) if(~T[o].ch[j]){
            o=T[o].ch[j]; break;
        }printf("%d\n",T[o].len-n+1);
    }return 0;
}

题意：给一个字符串。输出在原串中出现次数大于1的子串的出现次数。这些本质不同的子串按字典序大小排序输出次数。

一眼题？嗯。、后缀数组就行了、根据sa数组和height数组扫一遍。前后扫height数组。

反正n≤3000，没必要二分了。还要写rmq啥的多麻烦啊是吧、、然后就行了、感觉跑的蛮快的？

第一次加了fread和fwrite还变慢了、、

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=2000005;
int tmp1[maxn],tmp2[maxn],cs[maxn],cv[maxn],rank[maxn],height[maxn],sa[maxn];
char s[maxn],str[maxn];
inline bool cmp(int *r,int a,int b,int l){
    return  r[a]==r[b] && r[a+l]==r[b+l];
}inline void da(char *r,int *sa,int n,int m){
    int i,j,p,*x=tmp1,*y=tmp2,*t;
    for(i=0;i<m;i++)cs[i]=0;
    for(i=0;i<n;i++)cs[x[i]=r[i]]++;
    for(i=1;i<m;i++)cs[i]+=cs[i-1];
    for(i=n-1;i>=0;i--)sa[--cs[x[i]]]=i;
    for(j=1,p=1;p<n;j<<=1,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++)cv[i]=x[y[i]];
        for(i=0;i<m;i++)cs[i]=0;
        for(i=0;i<n;i++)cs[cv[i]]++;
        for(i=1;i<m;i++)cs[i]+=cs[i-1];
        for(i=n-1;i>=0;i--)sa[--cs[cv[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++;
    }
}inline void ch(char *r,int n){
    int i,j,k=0;
    for(i=0;i<n;i++)rank[sa[i]]=i;
    for(i=0;i<n;height[rank[i++]]=k)
        for(k=max(k-1,0),j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}int main(){
    int n;  scanf("%d%s",&n,str);
    for(int i=0;i<n;i++)str[i]++;   str[n++]=0;
    da(str,sa,n,256);   ch(str,n);
    for(int i=1;i<n;i++){
        for(int j=height[i]+1;sa[i]+j<n;j++){
            int l,r;
            for(l=i;l>=0 && height[l]>=j;l--);
            for(r=i+1;r<=n && height[r]>=j;r++);
            if(r-l<=1)continue;
            printf("%d\n",r-l);
        }
    }return 0;
}

题意：给你一个字符串。每次取出第一个字符或最后一个字符，放到新的字符串（初始为空）后面。求最小字典序的新字符串。

比如样例：ACDBCB。按这样的顺序拿：头尾尾尾头尾。这样得到ABCBCD。可以证明没有比它字典序更小的了。

一开始我先YY了个很傻比的贪心。第一个字符和最后一个字符比较。取小的。然后O(n)扫一遍。（画外音：你煞笔啊、gold的题目就给你这么水掉啊！、、）本着这种态度很快就发现样例都过不了。先取出A、B。然后是取队头的C还是队尾的C呢。这时就发现光比较这一个字符的大小是不够的。要比较整个字符串和整个字符串反转过来的字符串的字典序大小，才能决定取哪个。

那么想到了什么呢？很明显就是后缀数组。

把这个字符串反转一遍接在原字符串后面，中间加一个分隔符（最好是小于'A'的，比如'@'）。然后求出rank数组。

下标  0  1 2 3  4 5 6  7 8  9 10 11 12

字符  A C D B C B @ B C B D  C   A

那么维护两个指针，一个从0开始，一个从n+1（反转的字符串的起点）开始。比较rank的大小，每次取小的先输出。OK！

（fread、fwrite蛮好的、轻松rank3）

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=100000;
int tmp1[maxn],tmp2[maxn],cs[maxn],cv[maxn],rank[maxn],sa[maxn],str[maxn];
char s[maxn],buf[maxn],*p=buf,buf2[maxn],*o=buf2;
inline bool cmp(int *r,int a,int b,int l){
    return  r[a]==r[b] && r[a+l]==r[b+l];
}inline void da(char *r,int *sa,int n,int m){
    int i,j,p,*x=tmp1,*y=tmp2,*t;
    for(i=0;i<m;i++)cs[i]=0;
    for(i=0;i<n;i++)cs[x[i]=r[i]]++;
    for(i=1;i<m;i++)cs[i]+=cs[i-1];
    for(i=n-1;i>=0;i--)sa[--cs[x[i]]]=i;
    for(j=1,p=1;p<n;j<<=1,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++)cv[i]=x[y[i]];
        for(i=0;i<m;i++)cs[i]=0;
        for(i=0;i<n;i++)cs[cv[i]]++;
        for(i=1;i<m;i++)cs[i]+=cs[i-1];
        for(i=n-1;i>=0;i--)sa[--cs[cv[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++;
    }for(i=0;i<n;i++)rank[sa[i]]=i;
}int main(){
    fread(p,1,maxn,stdin);  int t=0,n=0;
    while(*p<'0'||*p>'9')p++;
    while(*p>='0'&&*p<='9')n=n*10+*p++-48;
    for(int i=1;i<=n;i++){ 
        while(*p<'A'||*p>'Z')p++;
        s[t++]=*p++; 
    }s[t++]='A'-1;
    for(int i=n-1;~i;i--)   s[t++]=s[i];    s[t++]='\0';
    da(s,sa,t,256);
    int j=0,k=n+1,c=0;
    for(int i=1;i<=n;i++)str[c++]=rank[j]>rank[k]?k++:j++;
    for(int i=0;i<n;i++){
        if(i&&i%80==0)*o++='\n';
        *o++=s[str[i]];
    }fwrite(buf2,1,o-buf2,stdout);
    return 0;
}