首页 > 代码库 > POJ 1509 Glass Beads---最小表示法
POJ 1509 Glass Beads---最小表示法
题意:
T组数据,每组数据给出一个字符串,求这个字符串的最小表示发(只要求输出起始位置坐标)
SAM入门题(检测板子是否正确)。
将字符串S加倍丢进SAM中,然后走字符串长度次,每次贪心的沿最小的边走,然后答案就是:sam.e[po].len-len+1
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 1001010 #define llg long long11 #define SIZE 26 12 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);13 llg n,m,T;14 15 char s[maxn];16 17 struct SAM18 {19 struct 20 {21 llg len,f/*parent边*/,ch[SIZE];22 void init()23 {24 len=0,f=-1;25 memset(ch,0xff,sizeof(ch));26 }27 }e[maxn<<1];28 llg idx,last;29 30 void init() {idx=last=0; e[idx++].init();}31 32 int newnode() {e[idx].init(); return idx++;}33 34 void add(llg c)35 {36 int end=newnode(),tmp=last;37 e[end].len=e[last].len+1;38 for (;tmp!=-1 && e[tmp].ch[c]==-1;tmp=e[tmp].f){e[tmp].ch[c]=end;}//跳parent tree的边,找到第一个具有c出边的点并停下,对于没有的点连出一条边权是c的边指向当前点(end)。39 if (tmp==-1) e[end].f=0;//如果没有任何一个点有权值为c的出边,则说明了相应字符c是第一次出现在自动机中。40 else41 {42 llg nxt=e[tmp].ch[c];43 if (e[tmp].len+1==e[nxt].len) e[end].f=nxt;//如果找到的第一个具有出边c的点的出边c左指向点的len=lastlen+1,则直接把新建点的parent边连向nxt点。44 else45 {46 llg np=newnode();47 e[np]=e[nxt];48 e[np].len=e[tmp].len+1;//新建点np49 e[nxt].f=e[end].f=np;50 for (;tmp!=-1 && e[tmp].ch[c]==nxt;tmp=e[tmp].f) {e[tmp].ch[c]=np;}//沿parent边往祖先走把所有原本连向nxt的带边权c的边改为连向np51 }//如果不满足MAX(s)+1=MAX(s[tmp][c])则新建点52 }53 last=end;54 }55 }sam;56 57 int main()58 {59 yyj("SAM");60 cin>>T;61 while (T--)62 {63 sam.init();64 scanf("%s",s);65 llg len=strlen(s);66 for (llg i=0;i<len;i++) sam.add(s[i]-‘a‘);67 for (llg i=0;i<len;i++) sam.add(s[i]-‘a‘);68 llg po=0;69 for (llg i=0;i<len;i++)70 for (llg j=0;j<26;j++)71 if (sam.e[po].ch[j]!=-1)72 {73 po=sam.e[po].ch[j];74 break;75 }76 printf("%lld\n",sam.e[po].len-len+1);77 }78 return 0;79 }
POJ 1509 Glass Beads---最小表示法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。