Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <vector>
- using namespace std;
- ifstream fin("input.txt");
- ofstream fout("output.txt");
- struct point
- {
- int choice;
- int go[27];
- int pr;
- };
- vector<point>v;
- int ans;
- void choice(int p, int val)
- {
- if(p==-1 || v[p].choice>1)return;
- v[p].choice=val;
- choice(v[p].pr, val);
- }
- void build(int p, string s)
- {
- v[p].go[s[0]-'a']=v.size();
- point x;
- for(int j=0;j<27;j++)
- x.go[j]=0;
- x.choice=1;
- x.pr=p;
- v.push_back(x);
- for(int i=1;i<s.length();i++)
- {
- x.pr=v.size()-1;
- v[x.pr].go[s[i]-'a']=v.size();
- v.push_back(x);
- }
- v[v.size()-1].go[26]=-1;
- v[p].choice++;
- choice(p,v[p].choice);
- }
- int bohr(int p, string sf,int pos=0, int l=0)
- {
- if(v[p].choice>1)l=0;
- if(pos==sf.length())
- {
- if(v[p].go[26]==0 && v[p].choice)return 0;
- return l;
- }
- if(v[p].go[sf[pos]-'a'])
- return bohr(v[p].go[sf[pos]-'a'],sf,pos+1,l+1);
- else
- {
- string s1;
- for(int i=pos;i<sf.length();i++)
- s1+=sf[i];
- build(p, s1);
- return l;
- }
- }
- int main()
- {
- if(true)
- {
- point x;
- x.pr=-1;
- for(int i=0;i<27;i++)
- x.go[i]=0;
- v.push_back(x);
- }
- string s;
- while(getline(fin,s))
- {
- ans+=s.length()+1;
- string s1;
- for(int i=0;i<s.length();i++)
- {
- if(s[i]<'a' || s[i]>'z')
- {
- int len=bohr(0,s1);
- if(len>1)ans-=len-2;
- cout<<s1<<" "<<len<<endl;
- s1.clear();
- }
- else
- s1+=s[i];
- }
- if(s1.length())
- {
- int len=bohr(0,s1);
- if(len>1)ans-=len-2;
- cout<<s1<<" "<<len<<endl;
- s1.clear();
- }
- }
- cout<<ans;
- fout<<ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement