Advertisement
Guest User

Untitled

a guest
Feb 25th, 2018
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 9.47 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. /*
  6.  
  7.  
  8. Весь алгоритм наступний
  9.  
  10. 1) считуємо весь текст
  11.  
  12. 2) всі лєві символи заміняємо на пробіл і зразу додаємо до відповіді так як слово це ЛИШЕ неперервний нижній регістр
  13.  
  14. 3) стрінгстрімим отриману строку і зчитуємо по одному слову
  15.  
  16. 4) для кожного слова треба чекнути за скільки ми б його могли найшвидше написати
  17. _ для цього підтримуємо бор всіх слів які були написані перед тим
  18. _ в вершині бору підтримуємо чи це кінець(leaf) і скільки слів мають такий префікс (kilk)
  19. _ проходимось по бору нашим поточним словом і находимо такі позиції
  20. _ р1 - позиція з якої у цієї строки є лише одна з спільним префіксом (тобто коли нам висвітить строку)
  21. _ р2 - чи дойшли ми до кінця по тій строці яку нам висвітило (тобто чи співпало все інше з підказкою)
  22. _ тоді нам вигідно коли ми в позиції р1 за один клік перейти в позицію р2 (за вийнятком того коли ці позиції співпали)
  23.  
  24. 5) додаємо строку яку ми щойно обробили в бор (якшо такої ще не було)
  25.  
  26. */
  27.  
  28.  
  29. char ss[300005]; //для считування
  30. int cnt; // скільки ми считали
  31. string s; // то шо ми считали тільки у вигляді строки
  32. int ans; // йобана в рот а шо ета такое ах да ето же сама відповідь!!
  33. map<string,bool> was; //чекаєм чи була така строка шоб 2 рази не додати в бор ту саму строку
  34.  
  35. bool ok_c(char c) //чекаєм чи символ нам канає для слова / от та шняга ет тіпа '
  36. { // |
  37. if(c==' ' || c=='\n' || c=='.' || c==',' || c=='?' || c=='!' || c=='\'' || c=='-')
  38. return 0; // ярік бля бачок потік, вилазь сука вилааазь
  39. return 1;
  40. }
  41.  
  42. struct item //ет для бору
  43. {
  44. int next[26]; //тут тіпа індекс наступного ітема якшо переходити по якомусь символу
  45. int leaf; //чи кінець
  46. int kilk; //кількість строк з таким префіксом
  47. item() //всьо по кд
  48. {
  49. for(int i=0;i<26;i++)
  50. next[i]=-1;
  51. leaf=0;
  52. kilk=0;
  53. }
  54. };
  55.  
  56. vector<item> borchik; //ось це той самий сука страшний нахуй бор...
  57.  
  58. int pp=1; //єбу шо за хуйня і звідки взялась
  59.  
  60. void add(string s) //додаємо строку в бор
  61. {
  62. was[s]=1; //мутим шо така строка є
  63. int v=0; // це тіпа нульова вершина бору з якої починаються всі перезоди (іншими словами це фіктивна вершина яка робить бор деревом)
  64. item temp; //чистейший образец ітему
  65. for(int i=0;i<s.size();i++)
  66. {
  67. int c=s[i]-'a'; //тичимо по якому символу в нас перехід
  68. if(borchik[v].next[c]==-1) //якшо такого переходу раніше не було
  69. {
  70. borchik[v].next[c]=borchik.size(); //створюємо новий ітем для цього переходу
  71. borchik[v].leaf=0; // так як такого переходу не було то це міг бути листок але оскільки ми шось додамо то це вже не може бути листком
  72. borchik.push_back(temp); // і тут ми закидуємо то шо ми створили в бор (ну і індекс якраз рівний borchik.size() до того як ми його закинули)
  73. }
  74. v=borchik[v].next[c]; //перейшли в наступний ітем (новостворений якшо його не було)
  75. borchik[v].kilk++; // і збільшили кількість строк які мають такйи префікс (для новоствореного ітема це буде 1)
  76.  
  77. ///cout<<(char)(c+(int)'a')<<":"<< borchik[v].kilk<<endl;
  78. }
  79. borchik[v].leaf=1; //позначили шо останній ітем стрічки це кінець (листочечок)
  80. }
  81.  
  82. int f(string s) //от на цій всій функції тримається моє очко
  83. {
  84. int v=0; //початок братца-борца
  85. int p1=-1,p2=-1; //позиції які треба найти
  86. for(int i=0;i<s.size();i++)
  87. {
  88. int c=s[i]-'a'; // куда перехід
  89.  
  90. if(borchik[v].next[c]==-1) //якшо такого переходу нема значить нам дальше прийдеться 100% писати вручну
  91. break;
  92.  
  93. v=borchik[v].next[c]; //перейшли в ітем того переходу і тичим
  94.  
  95. if(borchik[v].kilk==1 && p1==-1) //чи в тому ітемі є лише одна строка з таким префіксом(по якому ми і прийшли само собою) і чи є в нас вже р1 (*)
  96. p1=i; // найшли 1 позицію
  97.  
  98. if(borchik[v].leaf) //тичимо чи наш ітем це не кінець якогось слова
  99. p2=i; //якшо кінець то це могло бути лише то сьово яке нам МОГЛО висвітити
  100.  
  101. }
  102. ///cout<<s<<" "<<p1<<" "<<p2<<endl;
  103.  
  104. if(p1==-1 || p2==-1) return s.size(); // от тут ми і чекаєм чи це був кінець саме того слова шо нам висвітило якшо нам ваще шось висвітлювало
  105. // а висвітити могло тільки одне слово - те яке ми найши в позиції *
  106.  
  107. return min((int)s.size() , (int)s.size()-(p2-p1)+1); //ну і тут тіпа чек чи варто нам мутити той перехід бо це таки трікі кейс який можна найти зразу в семплах (шо мене чутка тривожить)
  108. //таке може бути тоді коли в нас є наприклад "abc" i "abcd" а ми пишемо "abcdkek" і коли ми напишемо "abcd" нам висвітить "abcd"
  109. //і ми як ваще не оптимальні дауни проєбемось просто клікнувши на то шо в нас вже написано
  110. // +1 в кінці це для кліку
  111. // (р2-р1) це те скільки ми пропустимо
  112. }
  113.  
  114. int main()
  115. {
  116. borchik.resize(1); //тут ми створили нашу ту саму фіктивну вершину
  117. while(scanf("%c",&ss[cnt])==1){cnt++;} //тут ми тіпа по символьно считуємо ВСЕ що приходить
  118. for(int i=0;i<cnt;i++)
  119. s+=ss[i]; //мутимо строку
  120. for(int i=0;i<cnt;i++)
  121. if(!ok_c(s[i]))
  122. {
  123. ans++; //лєве всьо зразу до відповіді
  124. s[i]=' '; //мутимо строку нормальною
  125. }
  126. stringstream gg(s); //тут запускаємо дфс
  127. string cur; // поточна пряма
  128. while(gg>>cur) // поки зчитується
  129. {
  130. ans+=f(cur); //до відповіді додаємо то за скільки мінімально ми можемо написати поточну строку
  131. if(!was.count(cur)) // якшо такої не було то її треба додати в борщец
  132. add(cur); //ммм а пахне
  133. }
  134. cout<<ans<<endl;
  135.  
  136. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement