fork(14) download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int alph=256;
  6.  
  7. const int INF=1e9;
  8. const int MPOW=16;
  9. const int N=1<<MPOW-1;
  10. const int N2=N<<1;
  11. struct sg_tree
  12. {
  13. int arr[N2];
  14.  
  15. void build(vector<int> x,int n)
  16. {
  17. fill(arr,arr+N2,INF);
  18. for(int i=0;i<n;i++)
  19. arr[i+N]=x[i];
  20. for(int i=N-1;i>0;i--)
  21. arr[i]=min(arr[i<<1],arr[(i<<1)+1]);
  22. }
  23.  
  24. int get_min(int c,int cl,int cr,int l,int r)
  25. {
  26. if(l==cl && r==cr)
  27. return arr[c];
  28. if(l>r)
  29. return INF;
  30. int cm=cl+cr>>1;
  31. return min(get_min(c<<1,cl,cm,l,min(r,cm)),get_min((c<<1)+1,cm+1,cr,max(l,cm+1),r));
  32. }
  33.  
  34. int get_min(int l,int r)
  35. {
  36. return get_min(1,0,N-1,l,r);
  37. }
  38. };
  39.  
  40. pair<vector<int>,vector<int>> compute(string &s)
  41. {
  42. int n=s.size();
  43. int maxn=n+alph;
  44.  
  45. vector<int> p(n),c(n),cnt(maxn,0);
  46. for(int i=0;i<n;i++)
  47. cnt[s[i]]++;
  48. for(int i=1;i<maxn;i++)
  49. cnt[i]+=cnt[i-1];
  50. for(int i=0;i<n;i++)
  51. p[--cnt[s[i]]]=i;
  52. int cl=0;
  53. c[p[0]]=cl;
  54. for(int i=1;i<n;i++)
  55. {
  56. if(s[p[i]]!=s[p[i-1]])cl++;
  57. c[p[i]]=cl;
  58. }
  59. vector<int> lcp(n,0);
  60. for(int i=1;i<n;i++)
  61. lcp[i]=c[p[i]]==c[p[i-1]];
  62. vector<int> pn(n),cn(n),lcpn(n);
  63. vector<int> rpos(n),lpos(n);
  64. sg_tree rmq;
  65. int k=1;
  66. while(k<n)
  67. {
  68. fill(begin(cnt),end(cnt),0);
  69. for(int i=0;i<n;i++)
  70. rpos[c[p[i]]]=i;
  71. for(int i=n-1;i>=0;i--)
  72. lpos[c[p[i]]]=i;
  73. for(int i=0;i<n;i++)
  74. {
  75. pn[i]=p[i]-k;
  76. if(pn[i]<0)pn[i]+=n;
  77. }
  78. for(int i=0;i<n;i++)
  79. cnt[c[i]]++;
  80. for(int i=1;i<maxn;i++)
  81. cnt[i]+=cnt[i-1];
  82. for(int i=n-1;i>=0;i--)
  83. p[--cnt[c[pn[i]]]]=pn[i];
  84. cl=0;
  85. cn[p[0]]=0;
  86. for(int i=1;i<n;i++)
  87. {
  88. int m1=(p[i]+k)%n,m2=(p[i-1]+k)%n;
  89. if(c[p[i]]!=c[p[i-1]] || c[m1]!=c[m2])cl++;
  90. cn[p[i]]=cl;
  91. }
  92. rmq.build(lcp,n);
  93. for(int i=1;i<n;i++)
  94. {
  95. int a=p[i],b=p[i-1];
  96. if(c[a]!=c[b])
  97. lcpn[i]=lcp[lpos[c[a]]];
  98. else
  99. {
  100. int aa=(a+k)%n,bb=(b+k)%n;
  101. if(c[aa]==c[bb])
  102. lcpn[i]=k<<1;
  103. else
  104. lcpn[i]=k+rmq.get_min(lpos[c[bb]]+1,rpos[c[aa]]);
  105. }
  106. lcpn[i]=min(n,lcpn[i]);
  107. }
  108. copy(begin(cn),end(cn),begin(c));
  109. copy(begin(lcpn),end(lcpn),begin(lcp));
  110. k<<=1;
  111. }
  112. return {p,lcp};
  113. }
  114.  
  115.  
  116. struct suffix_tree
  117. {
  118. struct edge
  119. {
  120. int from;
  121. int to;
  122. int next_vert;
  123. int suffix_here;
  124. };
  125.  
  126. struct vertex
  127. {
  128. vector<edge> go;
  129. };
  130.  
  131. string str;
  132. vector<vertex> data;
  133.  
  134. static bool comp(const edge &b,const char &a)
  135. {
  136. return 1;
  137. }
  138.  
  139. void build(string &s)
  140. {
  141. // Получим суффиксный массив строки, а также массив lcp
  142. pair<vector<int>,vector<int>> info=compute(s);
  143. vector<int> p=info.first,lcp=info.second;
  144.  
  145. int n=s.size();
  146. str=s;
  147.  
  148. // Будем хранить здесь стек рёбер, из которых мы ещё не вышли
  149. vector<int> p_vert;
  150. vector<int> p_edge;
  151. vector<int> p_dist;
  152.  
  153. // Добавим первую строку в дерево
  154. vertex v;
  155. edge e;
  156. e.from=p[0];
  157. e.to=n;
  158. e.next_vert=-1;
  159. e.suffix_here=p[0];
  160. v.go.push_back(e);
  161. data.push_back(v);
  162.  
  163. p_vert.push_back(0);
  164. p_edge.push_back(0);
  165. p_dist.push_back(0);
  166.  
  167. for(int i=1;i<n;i++)
  168. {
  169. int c_lcp=lcp[i];
  170. // Поднимаемся до lcp.
  171. while(p_dist.back()>c_lcp)
  172. {
  173. // Найдём минимальный суффикс, покрывающий ребро для ответа на задачу. Опционально.
  174. edge &E=data[p_vert.back()].go[p_edge.back()];
  175. if(E.next_vert+1)
  176. {
  177. int m=data[E.next_vert].go.size();
  178. for(int j=0;j<m;j++)
  179. E.suffix_here=min(E.suffix_here,data[E.next_vert].go[j].suffix_here);
  180. }
  181. // Удалим ребро из стека. Больше мы в него не вернёмся
  182. p_vert.pop_back();
  183. p_edge.pop_back();
  184. p_dist.pop_back();
  185. }
  186. vertex v;
  187. edge e;
  188. int c_v=p_vert.back();
  189. int c_e=p_edge.back();
  190. int At=data[c_v].go[c_e].from+c_lcp-p_dist.back(); // Индекс для разделения ребра
  191.  
  192. p_dist.push_back(c_lcp);
  193.  
  194. // Ребро, которое надо добавить
  195. e.next_vert=-1;
  196. e.suffix_here=p[i];
  197. e.from=p[i]+c_lcp;
  198. e.to=n;
  199.  
  200. // Либо добавляем ребро к вершине, либо разделяем текущее
  201. if(At==data[c_v].go[c_e].from)
  202. {
  203. data[c_v].go.push_back(e);
  204. p_vert.push_back(c_v);
  205. p_edge.push_back(data[c_v].go.size()-1);
  206. }
  207. else
  208. {
  209. v.go.push_back(data[c_v].go[c_e]);
  210. v.go.back().from=At;
  211. v.go.push_back(e);
  212. data.push_back(v);
  213. data[c_v].go[c_e].next_vert=data.size()-1;
  214. data[c_v].go[c_e].to=At;
  215. p_vert.push_back(data.size()-1);
  216. p_edge.push_back(1);
  217. }
  218. }
  219.  
  220. while(!p_dist.empty())
  221. {
  222. // Найдём минимальный суффикс, покрывающий ребро для ответа на задачу. Опционально.
  223. edge &E=data[p_vert.back()].go[p_edge.back()];
  224. if(E.next_vert+1)
  225. {
  226. int m=data[E.next_vert].go.size();
  227. for(int j=0;j<m;j++)
  228. E.suffix_here=min(E.suffix_here,data[E.next_vert].go[j].suffix_here);
  229. }
  230.  
  231. // Удалим ребро из стека. Больше мы в него не вернёмся
  232. p_vert.pop_back();
  233. p_edge.pop_back();
  234. p_dist.pop_back();
  235. }
  236. }
  237.  
  238. int search_str(string &s)
  239. {
  240. int n=s.size();
  241. int cur_v=0;
  242. int cur_e;
  243. char t;
  244.  
  245. for(int i=0;i<n;)
  246. {
  247. if(cur_v==-1)break;
  248. t=s[i];
  249. int cur_e;
  250. for(cur_e=0;cur_e<data[cur_v].go.size();cur_e++)
  251. if(str[data[cur_v].go[cur_e].from]>=t)break;
  252. for(int j=data[cur_v].go[cur_e].from;i<n && j<data[cur_v].go[cur_e].to;j++,i++)
  253. if(str[j]!=s[i])
  254. i=n+1;
  255. if(i==n)
  256. return data[cur_v].go[cur_e].suffix_here;
  257. cur_v=data[cur_v].go[cur_e].next_vert;
  258. }
  259. return -1;
  260. }
  261.  
  262. int print(int x)
  263. {
  264. if(x==-1)return 0;
  265. int ans=0;
  266. for(int i=0;i<data[x].go.size();i++)
  267. ans+=data[x].go[i].to-data[x].go[i].from+print(data[x].go[i].next_vert)-(data[x].go[i].to==str.size());
  268. return ans;
  269. }
  270. };
  271.  
  272. int main()
  273. {
  274. ios::sync_with_stdio(0);
  275. cin.tie(0);
  276. string a;
  277. cin>>a;
  278. a+='#';
  279. suffix_tree sf;
  280. sf.build(a);
  281. cout<<sf.print(0)<<endl;
  282. }
Success #stdin #stdout 0s 3628KB
stdin
Standard input is empty
stdout
0