（寫的都是初中小朋友czl早就切過的題……）

http://www.cnblogs.com/Lyush/p/3281546.html

?

POJ-1509?Glass Beads

UVA - 719?Glass Beads

題意：一個字符串可以將第一個字符放到最后一位，然后問不斷這樣做可以得到的字典序最小的字符串

sam模板題，copy一遍建個sam，然后直接在sam中跑一遍就行了。

sam記錄了字符串的所有后綴（也隨便記錄了字串），從root開始到每個接受態(tài)節(jié)點都是一個后綴（或多個），從root開始到每個節(jié)點都是一個子串（或多個）。由于copy一遍后把所有的情況的包括進(jìn)去了，那么只要跑len（原長）遍就行了！

constmaxn=30000; varstep,pre:array[0..maxn]of longint;son:array[0..maxn,0..25]of longint;tot,tail,t:longint;procedure add(x:longint); vari,j,k,np,p:longint; beginp:=tail;inc(tot);np:=tot;step[np]:=step[tail]+1;while (p>=0) and (son[p,x]=-1) do beginson[p,x]:=np;p:=pre[p];end;tail:=np;if p<0 then pre[np]:=0elseif step[son[p,x]]=step[p]+1 thenpre[np]:=son[p,x]else beginj:=son[p,x];inc(tot);k:=tot;for i:=0 to 25 do son[k,i]:=son[j,i];step[k]:=step[p]+1;pre[k]:=pre[j];pre[j]:=k;pre[np]:=k;while (p>=0) and (son[p,x]=j) do beginson[p,x]:=k;p:=pre[p];end;end; end;procedure work; vars:ansistring;len,i,j,k,p:longint; beginreadln(s);len:=length(s);s:=s+s;for i:=1 to len<<1 doadd(ord(s[i])-97);p:=0;for i:=1 to len dofor j:=0 to 25 doif son[p,j]>=0 then beginp:=son[p,j];break;end;writeln(step[p]-len+1); end;beginreadln(t);while t>0 do begindec(t);fillchar(pre,sizeof(pre),255);fillchar(son,sizeof(son),255);fillchar(step,sizeof(step),0);tot:=0;tail:=0;work;end end. View Code

?

SPOJ-1811?Longest Common Substring

題意：求兩個字符串的最長公共字串。

（似乎做sa的時候做過？然后翻出sa的代碼，交上去光榮tle……sam虐殺sa！！）

繼續(xù)貼麗潔姐論文話：

給兩個長度小于100000的字符串A和B，求出他們的最長公共連續(xù)子串。 我們構(gòu)造出A的后綴自動機SAM
對于SAM的每個狀態(tài)s，令r為Right(s)中任意的一個元素，它代表的是結(jié)束位置在r的，長度在[Min(s),Max(s)]之間的所有子串。
我們不妨對狀態(tài)s，求出所有B的子串中，從任意r開始往前能匹配的最大長度L，那么min(L,Max(s))就可以更新答案了。 我們考慮用SAM讀入字符串B。 令當(dāng)前狀態(tài)為s，同時最大匹配長度為len 我們讀入字符x。如果s有標(biāo)號為x的邊，
那么s=trans(s,x),len = len+1 否則我們找到s的第一個祖先a，它有標(biāo)號為x的邊，令
s=trans(a,x),len=Max(a)+1。 如果沒有這樣的祖先，那么令s=root,len=0。 在過程中更新狀態(tài)的最大匹配長度（在這道題中我沒有理解這句話，直接像以前處理kmp一樣邊跑邊更新，后來寫多個串的最長公共子串時就因為這個wa了好久！） 注意到我們求的是對于任意一個Right集合中的r，最大的匹配長度。那么對于一個狀態(tài)s，它的結(jié)果自然也可以作為它Parent的結(jié)果，我們可以從底到上更新一遍。 然后問題就解決了。 constmaxn=400000; varson:array[0..maxn,0..25]of longint;pre,step:array[0..maxn]of longint;last,tot:longint;function addpoint:longint; vari:longint; begininc(tot);//pre[tot]:=-1;// for i:=0 to 25 do son[tot,i]:=0;exit(tot); end;procedure add(x:longint); vari,new,now,old,more:longint; beginnew:=addpoint;now:=last;step[new]:=step[now]+1;while (now>=0) and (son[now,x]=0) do beginson[now,x]:=new;now:=pre[now];end;last:=new;if now<0 then pre[new]:=0elseif step[son[now,x]]=step[now]+1 thenpre[new]:=son[now,x]else beginold:=son[now,x];more:=addpoint;for i:=0 to 25 do son[more,i]:=son[old,i];step[more]:=step[now]+1;pre[more]:=pre[old];pre[old]:=more;pre[new]:=more;while (now>=0) and (son[now,x]=old) do beginson[now,x]:=more;now:=pre[now];end;end; end;procedure work; vars:ansistring;now,max,long,i,j:longint; beginfillchar(pre,sizeof(pre),255);readln(s);for i:=1 to length(s) do add(ord(s[i])-97);readln(s);now:=0;max:=0;long:=0;for i:=1 to length(s) do beginj:=ord(s[i])-97;if son[now,j]<>0 then begininc(long);now:=son[now,j];endelse beginwhile (now>=0) and (son[now,j]=0) do now:=pre[now];if now<0 then beginlong:=0;now:=0;endelse beginlong:=step[now]+1;now:=son[now,j];end;end;if long>max then max:=long;end;writeln(max); end;beginwork; end. View Code

?

SPOJ-1812?Longest Common Substring II

題意：求多個字符串的最長公共字串。

還是以第一個字符串建個sam。然后其他字符串像上一道一樣跑sam。

那么狀態(tài)s，其他串對它的匹配長度分別是a1，a2，a3……an的話，狀態(tài)s的最長公共字符串就是min（a1，a2，a3……an，max（s））。

然后去最長的狀態(tài)就行了！

constmaxn=200033;varp,num,step,ans,pre:array[0..maxn]of longint;son:array[0..maxn,0..25]of longint;tot,last:longint;function max(x,y:longint):longint; beginif x<y then exit(y);exit(x); end;function min(x,y:longint):longint; beginif x<y then exit(x);exit(y); end;procedure add(x:longint); vari,now,new,more,old:longint; begininc(tot);new:=tot;now:=last;last:=new;step[new]:=step[now]+1;while (now>=0) and (son[now,x]=0) do beginson[now,x]:=new;now:=pre[now];end;if now<0 then pre[new]:=0else beginold:=son[now,x];if step[now]+1=step[old] then pre[new]:=oldelse begininc(tot);more:=tot;for i:=0 to 25 do son[more,i]:=son[old,i];step[more]:=step[now]+1;pre[more]:=pre[old];pre[old]:=more;pre[new]:=more;while (now>=0) and (son[now,x]=old) do beginson[now,x]:=more;now:=pre[now];end;end;end; end;procedure into; vars:ansistring;i,len:longint; begintot:=0;pre[0]:=-1;readln(s);len:=length(s);for i:=1 to len doadd(ord(s[i])-97);fillchar(num,sizeof(num),0);for i:=1 to tot do inc(num[step[i]]);for i:=1 to len do inc(num[i],num[i-1]);for i:=1 to tot do beginp[num[step[i]]]:=i;dec(num[step[i]]);end;for i:=1 to tot do beginnum[i]:=0;ans[i]:=step[p[i]];end; end;procedure work; vars:ansistring;i,j,now,long,x,answer,n:longint; beginwhile not eof do beginreadln(s);now:=0;long:=0;for i:=1 to length(s) do beginj:=ord(s[i])-97;if son[now,j]<>0 then beginnow:=son[now,j];inc(long);num[now]:=max(num[now],long);endelse beginwhile (now>=0) and (son[now,j]=0) do now:=pre[now];if now<0 then beginnow:=0;long:=0;endelse beginlong:=step[now]+1;now:=son[now,j];num[now]:=max(num[now],long);end;end;end;for i:=tot downto 1 do beginx:=p[i];step[x]:=min(step[x],num[x]);num[pre[x]]:=max(num[pre[x]],num[x]);num[x]:=0;end;end;answer:=0;for i:=1 to tot doif answer<step[i] then answer:=step[i];writeln(answer); end;begininto;work; end. View Code

?

?

SPOJ-8222?Substrings

題意：給一個字符串s，求長度為i（i屬于【1,len】)的出現(xiàn)次數(shù)最多的子串出現(xiàn)的次數(shù)（好繞）……

上一篇有提到子串出現(xiàn)的個數(shù)就是right集合的大小。

那么用那個方法就行了（其實不用dfs序，可以用拓?fù)浜屯芭?#xff0c;拓?fù)湟_多幾個數(shù)組，桶排不用……速度沒比過)

注意right樹中要用兒子更新父親，就是長度為i+1可以更新長度為i的值……

typearr=recordfrom,next:longint;end; constmaxn=600000; varedge:array[0..maxn]of arr;ans,step,first,sum,num,pre,p:array[0..maxn]of longint;son:array[0..maxn,0..25]of longint;tot,last,len,esum:longint;function max(x,y:longint):longint; beginif x>y then exit(x);exit(y); end;function addpoint:longint; begininc(tot);exit(tot); end;procedure addedge(j,k:longint); begininc(esum);edge[esum].from:=j;edge[esum].next:=first[k];first[k]:=esum;inc(num[j]); end;procedure add(x:longint); varnow,new,more,old,i:longint; beginnew:=addpoint;now:=last;step[new]:=step[now]+1;while (now>=0) and (son[now,x]=0) do beginson[now,x]:=new;now:=pre[now];end;last:=new;if now<0 then pre[now]:=0else beginold:=son[now,x];if step[old]=step[now]+1 thenpre[new]:=oldelse beginmore:=addpoint;for i:=0 to 25 do son[more,i]:=son[old,i];step[more]:=step[now]+1;pre[more]:=pre[old];pre[new]:=more;pre[old]:=more;while (now>=0) and (son[now,x]=old) do beginson[now,x]:=more;now:=pre[now];end;end;end; end;procedure into; vars:ansistring;i,j:longint; beginreadln(s);pre[0]:=-1;last:=0;len:=length(s);for i:=1 to len do add(ord(s[i])-97);for i:=1 to tot dofor j:=0 to 25 doif son[i,j]<>0 then addedge(i,son[i,j]); end;procedure work; varhead,tail,i,x,fa:longint; beginhead:=1;tail:=0;while last>=0 do beginsum[last]:=1;last:=pre[last];end;for i:=0 to tot doif num[i]=0 then begininc(tail);p[tail]:=i;end;while head<=tail do beginx:=p[head];i:=first[x];while i>0 do beginfa:=edge[i].from;inc(sum[fa],sum[x]);dec(num[fa]);if num[fa]=0 then begininc(tail);p[tail]:=fa;end;i:=edge[i].next;end;inc(head);end;for i:=1 to tot doans[step[i]]:=max(ans[step[i]],sum[i]);for i:=len-1 downto 1 doans[i]:=max(ans[i],ans[i+1]);for i:=1 to len dowriteln(ans[i]); end;begininto;work; end. View Code

?

SPOJ-7258?Lexicographical Substring Search

題意：給定一個字符串，取出所有的子串按照字典序排序并去重后，求第K大的子串。

先預(yù)處理出每個節(jié)點的所包含子串總數(shù)，然后對每個詢問在sam上爬一爬就行了！

由于spoj卡得緊，處理詢問的時候不能從0-25都掃一遍，要先記錄兒子的數(shù)量，具體看代碼吧。

constmaxn=200000;varstep,num,sum,pre,p:array[0..maxn]of longint;col,too,son:array[0..maxn,0..25]of longint;last,tot:longint;procedure add(x:longint); vari,new,now,more,old:longint; begininc(tot);new:=tot;now:=last;step[new]:=step[now]+1;last:=new;while (now>=0) and (son[now,x]=0)do beginson[now,x]:=new;now:=pre[now];end;if now<0 then pre[new]:=0else beginold:=son[now,x];if step[old]=step[now]+1 then pre[new]:=oldelse begininc(tot);more:=tot;for i:=0 to 25 do son[more,i]:=son[old,i];step[more]:=step[now]+1;pre[more]:=pre[old];pre[new]:=more;pre[old]:=more;while (now>=0) and (son[now,x]=old) do beginson[now,x]:=more;now:=pre[now];end;end;end; end;procedure into; vars:ansistring;i,j,x,len:longint; beginpre[0]:=-1;last:=0;tot:=0;readln(s);len:=length(s);for i:=1 to len do add(ord(s[i])-97);fillchar(num,sizeof(num),0);for i:=1 to tot do beginsum[i]:=1;inc(num[step[i]]);end;for i:=2 to len do inc(num[i],num[i-1]);for i:=1 to tot do beginp[num[step[i]]]:=i;dec(num[step[i]]);end;fillchar(num,sizeof(num),0);for i:=tot downto 0 do beginx:=p[i];for j:=0 to 25 doif son[x,j]<>0 then begininc(num[x]);col[x,num[x]]:=j;too[x,num[x]]:=son[x,j];inc(sum[x],sum[son[x,j]]);end;end;//for i:=0 to tot do writeln(sum[i]); end;procedure work; varq,n,i,k,now:longint;answer:ansistring; beginreadln(q);while q>0 do begindec(q);readln(n);answer:='';now:=0;while n>0 do beginfor i:=1 to num[now] do begink:=too[now,i];if sum[k]<n thendec(n,sum[k])else begindec(n);answer:=answer+chr(97+col[now,i]);now:=k;break;end;end;end;writeln(answer);end; end;begininto;work end. View Code

?

HDU-4622?Reincarnation

題意：給定一個字符串，多組詢問，每個詢問給一個區(qū)間，求出該區(qū)間內(nèi)共有多少個不同的子串。

如果是單個子串好處理&（sa和sam都可以嘛）。

但是現(xiàn)在要求區(qū)間。我們可以這樣考慮，每次按左端點以此往右端點建。比如當(dāng)前是【l，r】然后變成【l，r+1】的話，就是sam（【l，r】）變成sam（【l，r+1】）。多出的子串就是step【last】-step【pre【last】】（這個很重要，在統(tǒng)計時經(jīng)常用到這個式子）

然后就直接處理出所有區(qū)間就行了……（暴力到不敢相信）

constmaxn=5000; varans:array[0..2100,0..2100]of longint;pre,step:array[0..maxn]of longint;son:array[0..maxn,0..25]of longint;tot,last,t,n,len,i,j:longint;s:ansistring;function addpoint:longint; begininc(tot);pre[tot]:=-1;fillchar(son[tot],sizeof(son[tot]),0);addpoint:=tot end;procedure add(x:longint); vari,now,new,old,more:longint; beginnew:=addpoint;now:=last;last:=new;step[new]:=step[now]+1;while (now>=0) and (son[now,x]=0) do beginson[now,x]:=new;now:=pre[now];end;if now<0 then pre[new]:=0else beginold:=son[now,x];if step[old]=step[now]+1 then pre[new]:=oldelse beginmore:=addpoint;for i:=0 to 25 do son[more,i]:=son[old,i];step[more]:=step[now]+1;pre[more]:=pre[old];pre[old]:=more;pre[new]:=more;while (now>=0) and (son[now,x]=old) do beginson[now,x]:=more;now:=pre[now];end;end;end end;beginreadln(t);while t>0 do begindec(t);readln(s);len:=length(s);for i:=1 to len do begintot:=-1;last:=addpoint;ans[i,i-1]:=0;for j:=i to len do beginadd(ord(s[j])-97);ans[i,j]:=ans[i,j-1]+step[last]-step[pre[last]];end;end;readln(n);while n>0 do begindec(n);readln(i,j);writeln(ans[i,j]);end;end end. View Code

（當(dāng)然也可以快排詢問，我懶所以沒有做）

?

HDU-4641?K-string

題意：給定字符串，有m次操作，每次操作可以向該字符串末尾添加一個字符或者詢問在字符串中出現(xiàn)了至少K次的子串一共有多少個？

就是在插入字符后順便統(tǒng)計一下就行了，如果這個點出現(xiàn)次數(shù)大于k那么一定已經(jīng)在ans中了。

要注意的是在step【old】>step【now】+1時復(fù)制點時，出現(xiàn)次數(shù)要也一起復(fù)制過去……

constmaxn=500000; varstep,num,pre:array[0..maxn]of longint;son:array[0..maxn,0..25]of longint;ans,tot,last,n,m,kk,i,j:longint;ch:char;s:ansistring;function addpoint:longint; vari:longint; begininc(tot);pre[tot]:=-1;step[tot]:=0;num[tot]:=0;for i:=0 to 25 doson[tot,i]:=0;addpoint:=tot; end;procedure add(x:longint); vari,now,new,more,old:longint; beginnew:=addpoint;now:=last;last:=new;step[new]:=step[now]+1;while (now>=0) and (son[now,x]=0) do beginson[now,x]:=new;now:=pre[now];end;if now<0 then pre[new]:=0else beginold:=son[now,x];if step[old]=step[now]+1 then pre[new]:=oldelse beginmore:=addpoint;for i:=0 to 25 do son[more,i]:=son[old,i];step[more]:=step[now]+1;num[more]:=num[old];pre[more]:=pre[old];pre[old]:=more;pre[new]:=more;while (now>=0) and (son[now,x]=old) do beginson[now,x]:=more;now:=pre[now];end;end;end;now:=last;while (now>0) and (num[now]<kk) do begininc(num[now]);if num[now]=kk thenans:=ans+step[now]-step[pre[now]];now:=pre[now];end; end;beginwhile not eof do beginreadln(n,m,kk);tot:=-1;last:=addpoint;ans:=0;readln(s);for i:=1 to length(s) doadd(ord(s[i])-97);while m>0 do begindec(m);read(j);if j=1 then beginread(ch);read(ch);add(ord(ch)-97);{for i:=0 to tot do beginwrite(i,':');for j:=0 to 25 dowrite(son[i,j],' ');writeln;end; }endelsewriteln(ans);readln;end;end end. View Code

?

待填之坑

SPOJ-8747. Substrings II && BZOJ-2555: SubString ( Suffix Automaton + Link Cut Tree )/BZOJ 2555 Substring （要lct嚇傻）

BZOJ 3238 AHOI2013 差異 后綴自動機

BZOJ 2882 工藝 后綴自動機

?

2015.04.14……看看人家學(xué)習(xí)的深度……唉，還是太弱了?http://www.cnblogs.com/zyfzyf/p/4397216.html#3161819

轉(zhuǎn)載于:https://www.cnblogs.com/Macaulish/p/4296557.html

總結(jié)

以上是生活随笔為你收集整理的后缀自动机习题合集的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。