API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jul 17th, 2018
69
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 9.73 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define mp make_pair
  6. #define ff first
  7. #define ss second
  8. #define xd puts("XD")
  9. #define endl puts("")
  10. #define ub upper_bound
  11. #define lb lower_bound
  12. #define MAXN 500005
  13.  
  14. typedef long long int ll;
  15.  
  16. int n, kon, l, wynik, gdzie, ile;
  17. char s[MAXN];
  18. ll H1=37, H2=41, h1[MAXN], h2[MAXN], pot1[MAXN], pot2[MAXN], M1=1000000009, M2=1000696969;
  19. bool czy[MAXN];
  20.  
  21. int bns3(int pocz, int koniec)
  22. {
  23. int sr=(pocz+koniec)/2;
  24. ll hs1=h1[kon+sr]-h1[kon]+M1*2;
  25. ll hs2=h2[kon+sr]-h2[kon]+M2*2;
  26. hs1%=M1;
  27. hs2%=M2;
  28. ll w1=h1[sr];
  29. ll w2=h2[sr];
  30. w1*=pot1[kon];
  31. w2*=pot2[kon];
  32. w1%=M1;
  33. w2%=M2;
  34. bool joker=false;
  35. //printf ("hs1=%lld w1=%lld hs2=%lld w2=%lld\n", hs1, w1, hs2, w2);
  36. if (hs1==w1 && hs2==w2)
  37. {
  38. joker=true;
  39. }
  40. //printf ("bns3 pocz=%d koniec=%d sr=%d joker=%d\n", pocz, koniec, sr, joker);
  41. if (joker==false)
  42. {
  43. wynik=min(wynik, sr);
  44. }
  45. if (pocz<koniec)
  46. {
  47. if (joker==false)
  48. {
  49. return bns3(pocz, sr);
  50. }
  51. else
  52. {
  53. return bns3(sr+1, koniec);
  54. }
  55. }
  56. else
  57. {
  58. return wynik;
  59. }
  60. }
  61. int bns2(int pocz, int koniec, int k)
  62. {
  63. int sr=(pocz+koniec)/2;
  64. ll hs1=h1[sr];
  65. ll hs2=h2[sr];
  66. ll w1=h1[k+sr]-h1[k]+M1*2;
  67. ll w2=h2[k+sr]-h2[k]+M2*2;
  68. w1%=M1;
  69. w2%=M2;
  70. hs1*=pot1[k];
  71. hs2*=pot2[k];
  72. hs1%=M1;
  73. hs2%=M2;
  74. bool joker=false;
  75. //printf ("hs1=%lld w1=%lld hs2=%lld w2=%lld\n", hs1, w1, hs2, w2);
  76. if (hs1==w1 && hs2==w2)
  77. {
  78. joker=true;
  79. }
  80. //printf ("bns2 pocz=%d koniec=%d sr=%d joker=%d\n", pocz, koniec, sr, joker);
  81. if (joker==false)
  82. {
  83. wynik=min(wynik, sr);
  84. }
  85. if (pocz<koniec)
  86. {
  87. if (joker==false)
  88. {
  89. return bns2(pocz, sr, k);
  90. }
  91. else
  92. {
  93. return bns2(sr+1, koniec, k);
  94. }
  95. }
  96. else
  97. {
  98. return wynik;
  99. }
  100. }
  101. int bns1(int pocz, int koniec, int k)
  102. {
  103. int sr=(pocz+koniec)/2;
  104. ll hs1=h1[sr];
  105. ll hs2=h2[sr];
  106. ll w1=h1[(gdzie-1)*k+sr]-h1[(gdzie-1)*k]+M1*2;
  107. ll w2=h2[(gdzie-1)*k+sr]-h2[(gdzie-1)*k]+M2*2;
  108. w1%=M1;
  109. w2%=M2;
  110. hs1*=pot1[(gdzie-1)*k];
  111. hs2*=pot2[(gdzie-1)*k];
  112. hs1%=M1;
  113. hs2%=M2;
  114. bool joker=false;
  115. //printf ("hs1=%lld w1=%lld hs2=%lld w2=%lld\n", hs1, w1, hs2, w2);
  116. if (hs1==w1 && hs2==w2)
  117. {
  118. joker=true;
  119. }
  120. //printf ("bns1 pocz=%d koniec=%d sr=%d joker=%d\n", pocz, koniec, sr, joker);
  121. if (joker==false)
  122. {
  123. wynik=min(wynik, sr);
  124. }
  125. if (pocz<koniec)
  126. {
  127. if (joker==false)
  128. {
  129. return bns1(pocz, sr, k);
  130. }
  131. else
  132. {
  133. return bns1(sr+1, koniec, k);
  134. }
  135. }
  136. else
  137. {
  138. return wynik;
  139. }
  140. }
  141. int main()
  142. {
  143. ios_base::sync_with_stdio(0);
  144. cin.tie(0);
  145. cin >> s;
  146. n=strlen(s);
  147. //printf ("n=%d\n", n);
  148. for (int i=n; i>=1; i--)
  149. {
  150. s[i]=s[i-1];
  151. }
  152. pot1[0]=pot2[0]=1;
  153. for (int i=1; i<=n; i++)
  154. {
  155. pot1[i]=pot1[i-1]*H1;
  156. pot1[i]%=M1;
  157. pot2[i]=pot2[i-1]*H2;
  158. pot2[i]%=M2;
  159. h1[i]=h1[i-1]+pot1[i]*(int(s[i])-96);
  160. h1[i]%=M1;
  161. h2[i]=h2[i-1]+pot2[i]*(int(s[i])-96);
  162. h2[i]%=M2;
  163. }
  164. for (int k=1; k<n; k++)
  165. {
  166. l=n/k;
  167. kon=l*k;
  168. //printf ("------------------------k=%d l=%d kon=%d------------------------------\n", k, l, kon);
  169. if (l==1)
  170. {
  171. //puts ("CASE 1");
  172. ll hs1=h1[n]-h1[kon]+M1*2;
  173. ll hs2=h2[n]-h2[kon]+M2*2;
  174. hs1%=M1;
  175. hs2%=M2;
  176. ll w1=h1[n-kon];
  177. ll w2=h2[n-kon];
  178. w1*=pot1[kon];
  179. w2*=pot2[kon];
  180. w1%=M1;
  181. w2%=M2;
  182. if (hs1==w1 && hs2==w2)
  183. {
  184. //puts ("ROWNE");
  185. czy[k]=true;
  186. }
  187. else
  188. {
  189. //puts ("ROZNE");
  190. wynik=n+1;
  191. int gg=bns3(1, n-kon);
  192. //printf ("gg=%d\n", gg);
  193. hs1=h1[n]-h1[kon+gg]+M1*2;
  194. hs2=h2[n]-h2[kon+gg]+M2*2;
  195. hs1%=M1;
  196. hs2%=M2;
  197. w1=h1[n-kon]-h1[gg]+M1*2;
  198. w2=h2[n-kon]-h2[gg]+M2*2;
  199. w1%=M1;
  200. w2%=M2;
  201. w1*=pot1[kon];
  202. w2*=pot2[kon];
  203. w1%=M1;
  204. w2%=M2;
  205. if (hs1==w1 && hs2==w2)
  206. {
  207. //puts ("OK");
  208. czy[k]=true;
  209. }
  210. }
  211. }
  212. else if (l==2)
  213. {
  214. //puts ("CASE 2");
  215. bool czy12, czy23, czy13;
  216. czy12=czy23=czy13=false;
  217. {
  218. ll hs1=h1[k];
  219. ll hs2=h2[k];
  220. ll w1=h1[2*k]-h1[k]+M1*2;
  221. ll w2=h2[2*k]-h2[k]+M2*2;
  222. w1%=M1;
  223. w2%=M2;
  224. hs1*=pot1[k];
  225. hs2*=pot2[k];
  226. hs1%=M1;
  227. hs2%=M2;
  228. if (hs1==w1 && hs2==w2)
  229. {
  230. czy12=true;
  231. }
  232. }
  233. {
  234. ll hs1=h1[n]-h1[kon]+M1*2;
  235. ll hs2=h2[n]-h2[kon]+M2*2;
  236. hs1%=M1;
  237. hs2%=M2;
  238. ll w1=h1[n-kon];
  239. ll w2=h2[n-kon];
  240. w1*=pot1[kon];
  241. w2*=pot2[kon];
  242. w1%=M1;
  243. w2%=M2;
  244. if (hs1==w1 && hs2==w2)
  245. {
  246. czy13=true;
  247. }
  248. }
  249. {
  250. ll hs1=h1[n]-h1[kon]+M1*2;
  251. ll hs2=h2[n]-h2[kon]+M2*2;
  252. hs1%=M1;
  253. hs2%=M2;
  254. ll w1=h1[n-kon+k]-h1[k]+M1*2;
  255. ll w2=h2[n-kon+k]-h2[k]+M2*2;
  256. w1%=M1;
  257. w2%=M2;
  258. w1*=pot1[kon-k];
  259. w2*=pot2[kon-k];
  260. w1%=M1;
  261. w2%=M2;
  262. if (hs1==w1 && hs2==w2)
  263. {
  264. czy23=true;
  265. }
  266. }
  267. //printf ("czy12=%d czy13=%d czy23=%d\n", czy12, czy13, czy23);
  268. if (czy12==true && czy13==true && czy23==true)
  269. {
  270. //puts ("WSZYSTKIE");
  271. czy[k]=true;
  272. }
  273. else if (czy12==true)
  274. {
  275. //puts ("BLAD W 3");
  276. wynik=n+1;
  277. int gg=bns3(1, n-kon);
  278. //printf ("gg=%d\n", gg);
  279. ll hs1=h1[n]-h1[kon+gg]+M1*2;
  280. ll hs2=h2[n]-h2[kon+gg]+M2*2;
  281. hs1%=M1;
  282. hs2%=M2;
  283. ll w1=h1[n-kon]-h1[gg]+M1*2;
  284. ll w2=h2[n-kon]-h2[gg]+M2*2;
  285. w1%=M1;
  286. w2%=M2;
  287. w1*=pot1[kon];
  288. w2*=pot2[kon];
  289. w1%=M1;
  290. w2%=M2;
  291. if (hs1==w1 && hs2==w2)
  292. {
  293. //puts ("OK");
  294. czy[k]=true;
  295. }
  296. }
  297. else if (czy13==true || czy23==true)
  298. {
  299. //puts ("OK W 3");
  300. wynik=n+1;
  301. int gg=bns2(1, k, k);
  302. //printf ("gg=%d\n", gg);
  303. ll hs1=h1[k]-h1[gg]+M1*2;
  304. ll hs2=h2[k]-h2[gg]+M2*2;
  305. hs1%=M1;
  306. hs2%=M2;
  307. ll w1=h1[2*k]-h1[k+gg]+M1*2;
  308. ll w2=h2[2*k]-h2[k+gg]+M2*2;
  309. w1%=M1;
  310. w2%=M2;
  311. hs1*=pot1[k];
  312. hs2*=pot2[k];
  313. hs1%=M1;
  314. hs2%=M2;
  315. if (hs1==w1 && hs2==w2)
  316. {
  317. //puts ("OK");
  318. czy[k]=true;
  319. }
  320. }
  321. }
  322. else
  323. {
  324. //puts ("CASE 3");
  325. gdzie=0;
  326. ll hs1=h1[k];
  327. ll hs2=h2[k];
  328. ll w1=h1[2*k]-h1[k]+M1*2;
  329. ll w2=h2[2*k]-h2[k]+M2*2;
  330. w1%=M1;
  331. w2%=M2;
  332. ll z1=h1[3*k]-h1[2*k]+M1*2;
  333. ll z2=h2[3*k]-h2[2*k]+M2*2;
  334. z1%=M1;
  335. z2%=M2;
  336. ll p1=-1, p2=-1;
  337. hs1*=pot1[2*k];
  338. hs2*=pot2[2*k];
  339. w1*=pot1[k];
  340. w2*=pot2[k];
  341. hs1%=M1;
  342. hs2%=M2;
  343. w1%=M1;
  344. w2%=M2;
  345. if (hs1==w1 && hs2==w2)
  346. {
  347. p1=hs1;
  348. p2=hs2;
  349. }
  350. if (hs1==z1 && hs2==z2)
  351. {
  352. p1=hs1;
  353. p2=hs2;
  354. }
  355. if (w1==z1 && w2==z2)
  356. {
  357. p1=w1;
  358. p2=w2;
  359. }
  360. //printf ("p1=%lld p2=%lld hs1=%lld w1=%lld z1=%lld hs2=%lld w2=%lld z2=%lld\n", p1, p2, hs1, w1, z1, hs2, w2, z2);
  361. for (int i=k; i<=kon; i+=k)
  362. {
  363. ll o1=p1, o2=p2;
  364. hs1=h1[i]-h1[i-k]+M1*2;
  365. hs2=h2[i]-h2[i-k]+M2*2;
  366. hs1%=M1;
  367. hs2%=M2;
  368. if (i==k)
  369. {
  370. hs1*=pot1[2*k];
  371. hs2*=pot2[2*k];
  372. hs1%=M1;
  373. hs2%=M2;
  374. }
  375. if (i==2*k)
  376. {
  377. hs1*=pot1[k];
  378. hs2*=pot2[k];
  379. hs1%=M1;
  380. hs2%=M2;
  381. }
  382. if (i>3*k)
  383. {
  384. p1*=pot1[i-3*k];
  385. p2*=pot2[i-3*k];
  386. p1%=M1;
  387. p2%=M2;
  388. }
  389. if (p1!=hs1 || p2!=hs2)
  390. {
  391. //printf ("PELNY OKRES NR %d JEST ZLY\n", i/k);
  392. if (gdzie==0)
  393. {
  394. gdzie=i/k;
  395. }
  396. else
  397. {
  398. gdzie=M2;
  399. }
  400. }
  401. p1=o1;
  402. p2=o2;
  403. }
  404. if (gdzie!=1)
  405. {
  406. hs1=h1[n]-h1[kon]+M1*2;
  407. hs2=h2[n]-h2[kon]+M2*2;
  408. hs1%=M1;
  409. hs2%=M2;
  410. w1=h1[n-kon];
  411. w2=h2[n-kon];
  412. w1*=pot1[kon];
  413. w2*=pot2[kon];
  414. w1%=M1;
  415. w2%=M2;
  416. }
  417. else
  418. {
  419. hs1=h1[n]-h1[kon]+M1*2;
  420. hs2=h2[n]-h2[kon]+M2*2;
  421. hs1%=M1;
  422. hs2%=M2;
  423. w1=h1[n-kon+k]-h1[k]+M1*2;
  424. w2=h2[n-kon+k]-h2[k]+M2*2;
  425. w1%=M1;
  426. w2%=M2;
  427. w1*=pot1[kon-k];
  428. w2*=pot2[kon-k];
  429. w1%=M1;
  430. w2%=M2;
  431. }
  432. if (hs1!=w1 || hs2!=w2)
  433. {
  434. //printf ("NIEPELNY JEST ZLY\n");
  435. if (gdzie==0)
  436. {
  437. gdzie=l+1;
  438. }
  439. else
  440. {
  441. gdzie=M2;
  442. }
  443. }
  444. if (gdzie==0)
  445. {
  446. czy[k]=true;
  447. }
  448. else if (gdzie<M2)
  449. {
  450. //printf ("BYL TYLKO JEDEN BLAD, W gdzie=%d\n", gdzie);
  451. if (gdzie==l+1)
  452. {
  453. //puts ("NIEPELNY OKRES");
  454. wynik=n+1;
  455. int gg=bns3(1, n-kon);
  456. //printf ("gg=%d\n", gg);
  457. hs1=h1[n]-h1[kon+gg]+M1*2;
  458. hs2=h2[n]-h2[kon+gg]+M2*2;
  459. hs1%=M1;
  460. hs2%=M2;
  461. w1=h1[n-kon]-h1[gg]+M1*2;
  462. w2=h2[n-kon]-h2[gg]+M2*2;
  463. w1%=M1;
  464. w2%=M2;
  465. w1*=pot1[kon];
  466. w2*=pot2[kon];
  467. w1%=M1;
  468. w2%=M2;
  469. if (hs1==w1 && hs2==w2)
  470. {
  471. //puts ("OK");
  472. czy[k]=true;
  473. }
  474. }
  475. else
  476. {
  477. //puts ("NIEPELNY");
  478. wynik=n+1;
  479. int gg;
  480. if (gdzie<=2)
  481. {
  482. //puts ("<=2");
  483. gg=bns2(1, k, k);
  484. //printf ("gg=%d\n", gg);
  485. hs1=h1[k]-h1[gg]+M1*2;
  486. hs2=h2[k]-h2[gg]+M2*2;
  487. hs1%=M1;
  488. hs2%=M2;
  489. w1=h1[2*k]-h1[k+gg]+M1*2;
  490. w2=h2[2*k]-h2[k+gg]+M2*2;
  491. w1%=M1;
  492. w2%=M2;
  493. hs1*=pot1[k];
  494. hs2*=pot2[k];
  495. hs1%=M1;
  496. hs2%=M2;
  497. if (hs1==w1 && hs2==w2)
  498. {
  499. //puts ("OK");
  500. czy[k]=true;
  501. }
  502. }
  503. else
  504. {
  505. //puts (">3");
  506. gg=bns1(1, k, k);
  507. //printf ("gg=%d\n", gg);
  508. hs1=h1[k]-h1[gg]+M1*2;
  509. hs2=h2[k]-h2[gg]+M2*2;
  510. hs1%=M1;
  511. hs2%=M2;
  512. w1=h1[gdzie*k]-h1[(gdzie-1)*k+gg]+M1*2;
  513. w2=h2[gdzie*k]-h2[(gdzie-1)*k+gg]+M2*2;
  514. w1%=M1;
  515. w2%=M2;
  516. hs1*=pot1[(gdzie-1)*k];
  517. hs2*=pot2[(gdzie-1)*k];
  518. hs1%=M1;
  519. hs2%=M2;
  520. if (hs1==w1 && hs2==w2)
  521. {
  522. //puts ("OK");
  523. czy[k]=true;
  524. }
  525. }
  526. }
  527. }
  528. }
  529. }
  530. for (int i=1; i<=n; i++)
  531. {
  532. if (czy[i]==true)
  533. {
  534. ile++;
  535. }
  536. }
  537. printf ("%d\n", ile);
  538. for (int i=1; i<=n; i++)
  539. {
  540. if (czy[i]==true)
  541. {
  542. printf ("%d ", i);
  543. }
  544. }
  545. return 0;
  546. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!