Advertisement
Guest User

Untitled

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