程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> POJ 1509 Glass Beads 後綴自動機

POJ 1509 Glass Beads 後綴自動機

編輯:關於C++

題目大意:給出一個環形的字符串,問從哪裡開始是的這個字符串的字典序最小。

 

思路:最小表示法和後綴自動機的裸題,不過我是為了學後綴自動機才寫的這個題,就沒有去學最小表示法。

做法很簡單,先建立一個後綴自動機,然後從根開始沿tranc指針從a->z走len次到達的點就是字典序最小的字符串的結尾點,求起始點只要減一下長度再+1即可。

 

對於後綴自動機的理解:www.2cto.com

 

CODE:
 

#include 
#include 
#include 
#include 
#define MAX 10010
using namespace std;

struct Complex{
	Complex *tranc[26],*father;
	short len;
}mempool[MAX << 2],*C = mempool,none,*nil = &none,*root,*last;
Complex *NewComplex(int _)
{
	C->len = _;
	fill(C->tranc,C->tranc + 26,nil);
	C->father = nil;
	return C++;
}

int T;
char s[MAX];

inline void Initialize()
{
	C = mempool;
	root = last = NewComplex(0);
}

inline void Add(int c)
{
	Complex *np = NewComplex(last->len + 1),*p = last;
	for(; p != nil && p->tranc[c] == nil; p = p->father)
		p->tranc[c] = np;
	if(p == nil)	np->father = root;
	else {
		Complex *q = p->tranc[c];
		if(q->len == p->len + 1)	np->father = q;
		else {
			Complex *nq = NewComplex(p->len + 1);
			nq->father = q->father;
			q->father = np->father = nq;
			memcpy(nq->tranc,q->tranc,sizeof(q->tranc));
			for(; p != nil && p->tranc[c] == q; p = p->father)
				p->tranc[c] = nq;
		}
	}
	last = np;
}

int main()
{
	for(cin >> T; T--;) {
		Initialize();
		scanf(%s,s);
		int length = strlen(s);
		for(int i = 0; i < length; ++i)
			Add(s[i] - 'a');
		for(int i = 0; i < length; ++i)
			Add(s[i] - 'a');
		Complex *now = root;
		for(int i = 0; i < length; ++i)
			for(int j = 0; j < 26; ++j)
				if(now->tranc[j] != nil) {
					now = now->tranc[j];
					break;
				}
		printf(%d
,now->len - length + 1);
	}
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved