vijos1437 简单的口令
链
解
打算去清远前清理桌面,于是发现了这个GDOI遗留下的未完成品。
最小表示法什么的,虽说有专门的算法,不过SAM用起来似乎更顺手。直接两倍原串后按字典序跑一遍就行了。
但那个神奇的算法还是找个时间研究一下吧。
RE了六次,WA了两次。
原因:变量名打错;字符串被分割称多行却无告知。
呃,几乎每次都是变量名打错而出错的呢。
码
#include <iostream>
#include <cstring>
using namespace std;
namespace DEL
{
template<int maxn, int sigma = 26>
class Suffix_Automaton
{
private:
struct Node
{
Node *fail;
Node *ch[sigma];
int len;
Node(){memset(ch, 0, sizeof ch);}
} *head, *tail, pool[maxn * 2];
int cnt, len;
inline int idx(char c)
{
return c - 'a';
}
public:
void init(int l)
{
//memset(&pool, 0, sizeof pool);
head = tail = &pool[0];
cnt = 1;
len = l;
}
void add(char c)
{
int id = idx(c);
Node *p = tail, *newnode = &pool[cnt++];
newnode -> len = p -> len + 1;
tail = newnode;
for(; p && !p -> ch[id]; p = p -> fail)
p -> ch[id] = newnode;
if(!p)
newnode -> fail = head;
else if(p -> len + 1 == p -> ch[id] -> len)
newnode -> fail = p -> ch[id];
else
{
Node *q = p -> ch[id], *r = &pool[cnt++];
*r = *q;
r -> len = p -> len + 1;
q -> fail = newnode -> fail = r;
for(; p && p -> ch[id] == q; p = p -> fail)
p -> ch[id] = r;
}
}
int go()
{
Node *p = head;
for(int i = 0; i < len; i++)
for(int j = 0; j < sigma; j++)
{
if(p -> ch[j])
{
p = p -> ch[j];
break;
}
}
return p -> len - len;
}
};
}
DEL::Suffix_Automaton<1000000> SAM;
int main()
{
int l;
cin>>l;
string s;
cin>>s;
string s1;
while(cin>>s1)
s += s1;
SAM.init(l);
s += s;
for(unsigned int i = 0; i < s.length(); i++)
SAM.add(s[i]);
cout<<SAM.go()<<endl;
return 0;
}