【SAM】BZOJ2882-工艺

【题目大意】

求一个循环数列的最小表示法。

【思路】

最小表示法的正解：★

SAM乱搞，和前面的POJ那道一样。然而MLE了，当作学习一下map的用法^ ^

map的使用方法（来源：☆）

一、map的说明
  1   头文件
  #include   <map>

  2   定义
  map<string,   int>   my_Map;
  或者是typedef     map<string,   int>   MY_MAP;
  MY_MAP   my_Map;

  3   插入数据
  (1)   my_Map["a"]   =   1;
  (2)   my_Map.insert(map<string,   int>::value_type("b",2));
  (3)   my_Map.insert(pair<string,int>("c",3));
  (4)   my_Map.insert(make_pair<string,int>("d",4));

  4   查找数据和修改数据
  (1)   int   i   =   my_Map["a"];
            my_Map["a"]   =   i;
  (2)   MY_MAP::iterator   my_Itr;
            my_Itr.find("b");
            int   j   =   my_Itr->second;
            my_Itr->second   =   j;
  不过注意，键本身是不能被修改的，除非删除。

  5   删除数据
  (1)   my_Map.erase(my_Itr);
  (2)   my_Map.erase("c");
  还是注意，第一种情况在迭代期间是不能被删除的，道理和foreach时不能删除元素一样。

  6   迭代数据
  for   (my_Itr=my_Map.begin();   my_Itr!=my_Map.end();   ++my_Itr)   {}

  7   其它方法
  my_Map.size()               返回元素数目
  my_Map.empty()       判断是否为空
  my_Map.clear()           清空所有元素
  可以直接进行赋值和比较：=,   >,   >=,   <,   <=,   !=   等等

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<map>
 6 using namespace std;
 7 const int MAXN=300002;
 8 int n,k;
 9 struct SAM
10 {
11     int tot,last;
12     int step[MAXN<<2],pre[MAXN<<2];
13     map<int,int> next[MAXN<<2];
14     inline int newNode(int cnt)
15     {
16         step[++tot]=cnt;
17         pre[tot]=0;
18         next[tot].clear();
19         return tot;
20     }
21     
22     inline void extend(int x)
23     {
24         int p=last;
25         int np=newNode(step[last]+1);
26         map<int,int>::iterator pos;
27         while (p) 
28         {
29             pos=next[p].find(x);
30             if (pos!=next[p].end()) break;
31             next[p].insert(pair<int,int>(x,np));
32             p=pre[p];
33         }
34         if (!p) pre[np]=1;
35             else 
36             {
37                 int q=pos->second;
38                 if (step[np]==step[p]+1) pre[np]=q;
39                 else
40                 {
41                     int nq=newNode(step[p]+1);
42                     next[nq]=next[q];
43                     pre[nq]=pre[q];
44                     pre[q]=pre[np]=nq;
45                     while (p)
46                     {
47                         pos=next[p].find(x);
48                         if (pos->second!=q) break;
49                         pos->second=nq;
50                         p=pre[p];
51                     }
52                 }
53             }
54             last=np;
55     }
56     
57     inline void clear()
58     {
59         tot=0;
60         last=newNode(0);
61     }
62 }suf;
63 int a[MAXN];
64 
65 void init()
66 {
67     scanf("%d",&n);
68     suf.clear();
69     for (int i=0;i<n;i++)
70     {
71         scanf("%d",&a[i]);
72     }    
73     for (int i=0;i<n;i++)
74         suf.extend(a[i]);
75     for (int i=0;i<n;i++)
76         suf.extend(a[i]);
77 }
78 
79 void solve()
80 {
81     int j=1;
82     for (int i=0;i<n;i++)
83     {
84         map<int,int>::iterator pos=suf.next[j].begin();
85         printf("%d",pos->first);
86         if (i!=n-1) printf(" ");
87         j=pos->second;
88     }
89 }
90 
91 int main()
92 {
93     init();
94     solve();
95     return 0;
96 }