POJ1509-Glass Beads【SAM求最小表示】

dzy posted @ 2013年7月01日 10:54 in POJ with tags POJ 最小表示 字符串 SAM , 1762 阅读

拿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;
}
Avatar_small
Emma 说:
2023年1月20日 19:22

Accidentally I have come across this website and little bit confused about the details you have shared here. This program describes the details regarding Using SAM to find the diamond rings minimum representation of a string. I am looking here for more such updates regarding the program from here and keep sharing more updates on that.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter