SAM后缀自动机学习小记 Poj 1509 Glass Beads (字符串最小表示)

刺骨的言语ヽ痛彻心扉 2022-08-24 11:49 3阅读 0赞

SAM是给很神奇很难懂的东西，现在能照猫画虎的用一用，还有待深入研究

学习资料

[2012年noi冬令营陈立杰讲稿\_百度文库][2012_noi]

[后缀自动机(FHQ+Neroysq补完)\_19世纪30年代的空间\_百度空间][FHQ_Neroysq_19_30]

[\[转载\]后缀自动机学习总结\_littlerock\_新浪博客][littlerock]

[【字符串新武器】后缀自动机 - huyuncong的专栏][- huyuncong]

[字符串模板总结（五）：后缀自动机 - bly - 博客频道 - CSDN.NET][- bly - _ - CSDN.NET]

[【后缀自动机】 - 沐阳 - 博客园][- _ -]

**Poj 1509 Glass Beads**

题意：求一个字符串的最小表示法开头字符的位置，如果有多个，求最小的位置

字符串的最小表示有一个专门的优秀算法可以处理：[字符串的最小表示法 - whyorwhnt的专栏][- whyorwhnt]

用后缀自动机处理也不错。

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    const int N = 10005;
    
    class SAM
    {
    public:
    	struct Node {
    		int go[26];    //表示当前结点的出边
    		int pre, len;    //前继结点 当前结点的最长路径长度
    		void init () {
    			pre=-1, len=0;
    			memset(go, 0xff, sizeof (go));
    		}
    	};
    	Node sn[N<<1];
    	int idx, last;   //标号和上一个添加的结点
    	void init () {   //初始化SAM
    		idx = last = 0;
    		sn[idx++].init();
    	}
    	int newnode () {
    		sn[idx].init();
    		return idx++;
    	}
    	void extend (int c) {  //扩展结点
    		int end = newnode();
    		int tmp = last;    //上一个添加的结点
    		sn[end].len = sn[last].len + 1;
    		for (; tmp != -1 && sn[tmp].go[c] == -1; tmp = sn[tmp].pre) //对于没有到该字符的祖先结点添加到当前结点的边
    			sn[tmp].go[c] = end;
    		if (tmp == -1) sn[end].pre = 0; //若该字符第一次出现，添加到根结点的边
    		else {
    			int nxt = sn[tmp].go[c];
    			if (sn[tmp].len + 1 == sn[nxt].len) sn[end].pre = nxt; // 如果可接受点有向c的转移，且长度只加1，那么该孩子可以替代当前的end，并且end的双亲指向该孩子 
    			else {
    				int np = newnode();   //新建结点并将nxt信息复制
    				sn[np] = sn[nxt];
    				sn[np].len = sn[tmp].len + 1;
    				sn[end].pre = sn[nxt].pre = np; //设置np为end和nxt的前继节点
    				for (; tmp != -1 && sn[tmp].go[c] == nxt; tmp = sn[tmp].pre) //将指向nxt的tmp的祖先结点改为指向np
                        sn[tmp].go[c] = np;
    			}
    		}
    		last = end;
    	}
    	void build (char str[],int low)
    	{//传入参数:字符串和字符串中最小的字符
    		init();
    		int len=strlen(str);
    		for (int i=0;i<len;i++)
    			extend(str[i]-low);
    	}
    }sam;
    
    char str[2*N];
    
    int main ()
    {
    	int T,i;
    	scanf("%d", &T);
    	while (T--)
    	{
    		scanf("%s", str);
    		int len = strlen(str);
    		for (i=0;i<len;i++)
    			str[i+len]=str[i];
    		str[i+len]=0;
    		sam.build(str,'a');
            int p=0;
            for (i=0;i<len;i++) //从root开始跑,每次都跑最小编号的结点,在上面跑|S|个结点,然后输出当前结点的信息就行了
    			for (int j=0;j<26;j++) //跑编号最小的节点也就保证了整个字符串字典序最小，也就是最小表示
    				if (sam.sn[p].go[j] != -1)
    				{
    					p=sam.sn[p].go[j];
    					break;
    				}
    		printf("%d\n", sam.sn[p].len-len+1);
    	}
    	return 0;
    }

最小表示的代码：

#include <cstdio>
    #include <cstring>
    #define max(a,b) ((a)>(b)?(a):(b))
    #define min(a,b) ((a)<(b)?(a):(b))
    
    const int N = 10005;
    
    int minstr(char s[])
    {
    	int len=strlen(s);
    	int i=0,j=1;
    	while(i<=len-1 && j<=len-1)
    	{
    		int k=0;
    		while(k<=len-1 && s[(i+k)%len]==s[(j+k)%len])
    			k++;
    		if(k>=len)
    			break;
    		if(s[(i+k)%len]>s[(j+k)%len])
    			i=max(i+k+1,j+1);//此时s[i+1]到s[i+k]都不可能是最小字符串的开头，而且s[i+1]到s[j]也不可能是最小字符串的开头(s[i]开头的字符串与s[j]开头的字符串在比较，本身已经说明s[i]开头的字符串小于以s[i+1]开头到以s[j-1]开头的字符串了)
    		else
    			j=max(j+k+1,i+1);//同上道理
    	}
    	return min(i,j);
    }
    
    char str[N];
    
    int main ()
    {
    	int T;
    	scanf("%d", &T);
    	while (T--)
    	{
    		scanf("%s", str);
    		printf("%d\n",minstr(str)+1);
    	}
    	return 0;
    }

[2012_noi]: http://wenku.baidu.com/link?url=kGIuGPc4ls4Naod021QcvaeCGsva12Kb9jBw_DTBKzfDN35rdxzcjhCy59FYQBemzvb4p21Tu229bAyzdd97FdchJqSv9LKITYXuA55WppS
[FHQ_Neroysq_19_30]: http://hi.baidu.com/myidea/item/142c5cd45901a51820e25039
[littlerock]: http://blog.sina.com.cn/s/blog_6f0dd8ed0101ag1v.html
[- huyuncong]: http://blog.csdn.net/huyuncong/article/details/7583214
[- bly - _ - CSDN.NET]: http://blog.csdn.net/incredible_bly/article/details/12954699
[- _ -]: http://www.cnblogs.com/Lyush/archive/2013/08/25/3281546.html
[- whyorwhnt]: http://blog.csdn.net/whyorwhnt/article/details/9358789