链

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;
}