//input aadabbcdd
//output
//1 1 4 1 2 2 3 4
//aadabbcdd
#include<bits/stdc++.h>
using namespace std;
vector<int>encoding(string &s,map<string,int>&dictionary)
{
vector<int>v;
int num=1;
set<char>st;
for(int i=0;i<s.size();i++)
{
st.insert(s[i]);
}
for(auto u:st)
{
string ss="";
ss+=u;
dictionary[ss]=num;
num++;
}
string temp="";
for(int i=0;i<s.size();i++)
{
string last=temp;
temp+=s[i];
if(dictionary.find(temp)!=dictionary.end())
{
continue;
}
else
{
v.push_back(dictionary[last]);
dictionary[temp]=num;
temp="";
temp+=s[i];
num++;
}
}
if(temp!="")
{
dictionary[temp]=num;
num++;
}
return v;
}
void decoding(vector<int>v,map<string,int>dictionary,int num)
{
int lastpointer=0;
string s="";
map<int,string>dictionary1;
for(auto u:dictionary)
{
//cout<<u.first<<" "<<u.second<<endl;
dictionary1[u.second]=u.first;
}
string temp="";
for(int i=0;i<v.size();i++)
{
if(dictionary1.find(v[i])!=dictionary1.end())
{
s+=dictionary1[v[i]];
continue;
}
for(int j=lastpointer;j<s.size();j++)
{
string last=temp;
temp+=s[j];
lastpointer=j;
if(dictionary.find(temp)!=dictionary.end())
{
continue;
}
else
{
dictionary[temp]=num;
dictionary1[num]=temp;
cout<<temp<<" "<<num<<endl;
temp="";
temp+=s[j];
num++;
if(num-1==v[i])
{
s+=dictionary1[v[i]];
lastpointer=j;
}
}
}
if(temp!="")
{
dictionary[temp]=num;
dictionary1[num]=temp;
num++;
}
}
cout<<s<<endl;
}
int main()
{
string s;
cin>>s;
map<string,int>dictionary;
vector<int>encode=encoding(s,dictionary);
for(auto u:encode)
{
cout<<u<<" ";
}
dictionary.clear();
int num=1;
set<char>st;
for(int i=0;i<s.size();i++)
{
st.insert(s[i]);
}
for(auto u:st)
{
string ss="";
ss+=u;
dictionary[ss]=num;
num++;
}
string it="";
it+=s[s.size()-1];
encode.push_back(dictionary[it]);
cout<<endl;
decoding(encode,dictionary,st.size()+1);
return 0;
}
0 Comments