Advertisement
Guest User

Untitled

a guest
Feb 24th, 2018
235
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.03 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5.  
  6. struct point
  7. {
  8. int choice; //сколько потомков
  9. int go[26]; //потомки, индекс - букква
  10. int pr; //предок
  11. };
  12.  
  13. vector<point>v;
  14. int ans;
  15.  
  16. void choice(int p) //изменить чойс всех выше точки
  17. {
  18. if(p==-1)return;
  19. if(v[p].choice)return;
  20. v[p].choice=true;
  21. choice(v[p].pr);
  22. }
  23.  
  24. void build(int p, string s) //добавить слово s в потомки вершины p
  25. {
  26. v[p].go[s[0]-'a']=v.size();
  27. point x;
  28. x.choice=0;
  29. x.pr=p;
  30. v.push_back(x);
  31. for(int i=1;i<s.size();i++)
  32. {
  33. x.pr=v.size()-1;
  34. v[x.pr].go[s[i]-'a']=v.size();
  35. v.push_back(x);
  36. }
  37. v[p].choice++;
  38. }
  39.  
  40. int bohr(int p, string sf,int pos=0, int l=0)
  41. {
  42. if(v[p].choice>1)l=0;
  43. if(pos==sf.size())
  44. {
  45. if(v[p].choice)return 0;
  46. return l;
  47. }
  48. if(v[p].go[sf[l]-'a'])
  49. return bohr(v[p].go[sf[l]-'a'],sf,pos+1,l+1);
  50. else
  51. {
  52. string s1;
  53. s1.clear();
  54. for(int i=pos;i<sf.size();i++)
  55. s1[i-pos]=sf[i];
  56. build(p, s1);
  57. if(v[p].choice>1)l=0;
  58. return l;
  59. }
  60. }
  61.  
  62. int main()
  63. {
  64. if(true)
  65. {
  66. point x;
  67. v.push_back(x);
  68. }
  69. string s;
  70. while(cin>>s)
  71. {
  72. ans+=s.size()+1;
  73. string s1;
  74. s1.clear();
  75. int j=0;
  76. for(int i=0;i<s.size();i++)
  77. {
  78. //разделяем слово по знакам препинания
  79. if(s[i]<'a' || s[i]>'z')
  80. {
  81. int len=bohr(0,s1);
  82. if(len>0)ans-=len-1;
  83. s1.clear();
  84. j=0;
  85. }
  86. else
  87. {
  88. s1[j]=s[i];
  89. j++;
  90. }
  91. }
  92. if(s1.size())
  93. {
  94. int len=bohr(0,s1);
  95. if(len>0)ans-=len-1;
  96. s1.clear();
  97. }
  98. cout<<ans<<endl;
  99. }
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement