Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- /*
- Весь алгоритм наступний
- 1) считуємо весь текст
- 2) всі лєві символи заміняємо на пробіл і зразу додаємо до відповіді так як слово це ЛИШЕ неперервний нижній регістр
- 3) стрінгстрімим отриману строку і зчитуємо по одному слову
- 4) для кожного слова треба чекнути за скільки ми б його могли найшвидше написати
- _ для цього підтримуємо бор всіх слів які були написані перед тим
- _ в вершині бору підтримуємо чи це кінець(leaf) і скільки слів мають такий префікс (kilk)
- _ проходимось по бору нашим поточним словом і находимо такі позиції
- _ р1 - позиція з якої у цієї строки є лише одна з спільним префіксом (тобто коли нам висвітить строку)
- _ р2 - чи дойшли ми до кінця по тій строці яку нам висвітило (тобто чи співпало все інше з підказкою)
- _ тоді нам вигідно коли ми в позиції р1 за один клік перейти в позицію р2 (за вийнятком того коли ці позиції співпали)
- 5) додаємо строку яку ми щойно обробили в бор (якшо такої ще не було)
- */
- char ss[300005]; //для считування
- int cnt; // скільки ми считали
- string s; // то шо ми считали тільки у вигляді строки
- int ans; // йобана в рот а шо ета такое ах да ето же сама відповідь!!
- map<string,bool> was; //чекаєм чи була така строка шоб 2 рази не додати в бор ту саму строку
- bool ok_c(char c) //чекаєм чи символ нам канає для слова / от та шняга ет тіпа '
- { // |
- if(c==' ' || c=='\n' || c=='.' || c==',' || c=='?' || c=='!' || c=='\'' || c=='-')
- return 0; // ярік бля бачок потік, вилазь сука вилааазь
- return 1;
- }
- struct item //ет для бору
- {
- int next[26]; //тут тіпа індекс наступного ітема якшо переходити по якомусь символу
- int leaf; //чи кінець
- int kilk; //кількість строк з таким префіксом
- item() //всьо по кд
- {
- for(int i=0;i<26;i++)
- next[i]=-1;
- leaf=0;
- kilk=0;
- }
- };
- vector<item> borchik; //ось це той самий сука страшний нахуй бор...
- int pp=1; //єбу шо за хуйня і звідки взялась
- void add(string s) //додаємо строку в бор
- {
- was[s]=1; //мутим шо така строка є
- int v=0; // це тіпа нульова вершина бору з якої починаються всі перезоди (іншими словами це фіктивна вершина яка робить бор деревом)
- item temp; //чистейший образец ітему
- for(int i=0;i<s.size();i++)
- {
- int c=s[i]-'a'; //тичимо по якому символу в нас перехід
- if(borchik[v].next[c]==-1) //якшо такого переходу раніше не було
- {
- borchik[v].next[c]=borchik.size(); //створюємо новий ітем для цього переходу
- borchik[v].leaf=0; // так як такого переходу не було то це міг бути листок але оскільки ми шось додамо то це вже не може бути листком
- borchik.push_back(temp); // і тут ми закидуємо то шо ми створили в бор (ну і індекс якраз рівний borchik.size() до того як ми його закинули)
- }
- v=borchik[v].next[c]; //перейшли в наступний ітем (новостворений якшо його не було)
- borchik[v].kilk++; // і збільшили кількість строк які мають такйи префікс (для новоствореного ітема це буде 1)
- ///cout<<(char)(c+(int)'a')<<":"<< borchik[v].kilk<<endl;
- }
- borchik[v].leaf=1; //позначили шо останній ітем стрічки це кінець (листочечок)
- }
- int f(string s) //от на цій всій функції тримається моє очко
- {
- int v=0; //початок братца-борца
- int p1=-1,p2=-1; //позиції які треба найти
- for(int i=0;i<s.size();i++)
- {
- int c=s[i]-'a'; // куда перехід
- if(borchik[v].next[c]==-1) //якшо такого переходу нема значить нам дальше прийдеться 100% писати вручну
- break;
- v=borchik[v].next[c]; //перейшли в ітем того переходу і тичим
- if(borchik[v].kilk==1 && p1==-1) //чи в тому ітемі є лише одна строка з таким префіксом(по якому ми і прийшли само собою) і чи є в нас вже р1 (*)
- p1=i; // найшли 1 позицію
- if(borchik[v].leaf) //тичимо чи наш ітем це не кінець якогось слова
- p2=i; //якшо кінець то це могло бути лише то сьово яке нам МОГЛО висвітити
- }
- ///cout<<s<<" "<<p1<<" "<<p2<<endl;
- if(p1==-1 || p2==-1) return s.size(); // от тут ми і чекаєм чи це був кінець саме того слова шо нам висвітило якшо нам ваще шось висвітлювало
- // а висвітити могло тільки одне слово - те яке ми найши в позиції *
- return min((int)s.size() , (int)s.size()-(p2-p1)+1); //ну і тут тіпа чек чи варто нам мутити той перехід бо це таки трікі кейс який можна найти зразу в семплах (шо мене чутка тривожить)
- //таке може бути тоді коли в нас є наприклад "abc" i "abcd" а ми пишемо "abcdkek" і коли ми напишемо "abcd" нам висвітить "abcd"
- //і ми як ваще не оптимальні дауни проєбемось просто клікнувши на то шо в нас вже написано
- // +1 в кінці це для кліку
- // (р2-р1) це те скільки ми пропустимо
- }
- int main()
- {
- borchik.resize(1); //тут ми створили нашу ту саму фіктивну вершину
- while(scanf("%c",&ss[cnt])==1){cnt++;} //тут ми тіпа по символьно считуємо ВСЕ що приходить
- for(int i=0;i<cnt;i++)
- s+=ss[i]; //мутимо строку
- for(int i=0;i<cnt;i++)
- if(!ok_c(s[i]))
- {
- ans++; //лєве всьо зразу до відповіді
- s[i]=' '; //мутимо строку нормальною
- }
- stringstream gg(s); //тут запускаємо дфс
- string cur; // поточна пряма
- while(gg>>cur) // поки зчитується
- {
- ans+=f(cur); //до відповіді додаємо то за скільки мінімально ми можемо написати поточну строку
- if(!was.count(cur)) // якшо такої не було то її треба додати в борщец
- add(cur); //ммм а пахне
- }
- cout<<ans<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement