How many HDOJ2609

这题直接用最小表示法+trie就可以秒掉，但为了练习sam，就用牛刀杀次鸡 O(∩_∩)O~

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
#include <cctype>
#include <utility>   
#include <map>
#include <string>  
#include <climits> 
#include <set>
#include <string>    
#include <sstream>
#include <utility>   
#include <ctime>

using std::priority_queue;
using std::vector;
using std::swap;
using std::stack;
using std::sort;
using std::max;
using std::min;
using std::pair;
using std::map;
using std::string;
using std::cin;
using std::cout;
using std::set;
using std::queue;
using std::string;
using std::istringstream;
using std::make_pair;
using std::getline;
using std::greater;
using std::endl;
using std::multimap;
using std::deque;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PAIR;
typedef multimap<int, int> MMAP;

const int MAXN(210);
const int SIGMA_SIZE(2);
const int MAXM(110);
const int MAXE(300010);
const int MAXH(18);
const int INFI((INT_MAX-1) >> 1);
const int MOD(2520);
const ULL BASE(31);
const ULL LIM(1000000000000000ull);

struct SAM
{
    struct NODE
    {
        NODE *par, *ch[SIGMA_SIZE];
        int val;
    };
    NODE *root, *last;
    NODE pool[MAXN << 1];
    NODE *rear;
    void init()
    {
        last = root = pool;
        root->par = 0;
        memset(root->ch, 0, sizeof(root->ch));
        rear = pool+1;
    }
    NODE *newnode(int tv)
    {
        rear->val = tv;
        memset(rear->ch, 0, sizeof(rear->ch));
        return rear++;
    }
    void extend(int id)
    {
        NODE *p = last, *np = newnode(last->val+1);
        while(p && p->ch[id] == 0)
            p->ch[id] = np, p = p->par;
        if(p == 0)
            np->par = root;
        else
        {
            NODE *q = p->ch[id];
            if(p->val+1 == q->val)
                np->par = q;
            else
            {
                NODE *nq = newnode(p->val+1);
                memcpy(nq->ch, q->ch, sizeof(nq->ch));
                nq->par = q->par;
                q->par = nq;
                np->par = nq;
                while(p && p->ch[id] == q)
                    p->ch[id] = nq, p = p->par;
            }
        }
        last = np;
    }
};

struct TRIE
{
    int ch[1000010][SIGMA_SIZE];
    bool val[1000010];
    int size;
    void init()
    {
        memset(ch[0], 0, sizeof(ch[0]));
        val[0] = false;
        size = 1;
    }
    inline int idx(char temp)
    {
        return temp-'0';
    }
    bool insert(char *S)
    {
        int u = 0, id;
        for(; *S; ++S)
        {
            id = idx(*S);
            if(!ch[u][id])
            {
                memset(ch[size], 0, sizeof(ch[size]));
                val[size] = false;
                ch[u][id] = size++;
            }
            u = ch[u][id];
        }
        if(val[u])
            return false;
        val[u] = true;
        return true;
    }
};

SAM sam;
TRIE trie;
char str[210];

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        trie.init();
        int ans = 0;
        for(int i = 0; i < n; ++i)
        {
            scanf("%s", str);
            int len = strlen(str);
            memcpy(str+len, str, sizeof(str[0])*len);
            int tlen = len*2;
            sam.init();
            for(int i = 0; i < tlen; ++i)
                sam.extend(str[i]-'0');
            SAM::NODE *p = sam.root;
            for(int i = 0; i < len; ++i)
                if(p->ch[0])
                {
                    str[i] = '0';
                    p = p->ch[0];
                }
                else
                {
                    str[i] = '1';
                    p = p->ch[1];
                }
            str[len] = '\0';
            if(trie.insert(str))
                ++ans;
        }
        printf("%d\n", ans);
    }
    return 0;
}