#include using namespace std; typedef unsigned long long ull; const int N = 1e5 + 3; const int BASE = 313; string s, ans; int n; clock_t timer = clock(); mt19937 mt(953); ull pwr[N]; bool vis[N], first = true; inline bool time_left(){ return ((float)clock() - (float)timer) / (float)CLOCKS_PER_SEC <= 4.5; } void optimize_mult(int len){ string new_ans = ""; int cnt = 0, i; for(i = len; i < ans.size(); ++i){ if(ans[i] == ans[i - len]) ++cnt; else{ if(len + to_string(cnt / len + 1).size() + 3 < (cnt / len + 1) * len){ new_ans += "["; for(int j = i - cnt - len; j < i - cnt; ++j) new_ans += ans[j]; new_ans += "," + to_string(cnt / len + 1) + "]"; i += len - (cnt % len); --i; } else{ for(int j = i - cnt - len; j <= i - len; ++j) new_ans += ans[j]; } cnt = 0; } } if(len + to_string(cnt / len + 1).size() + 3 < (cnt / len + 1) * len){ new_ans += "["; for(int j = i - cnt - len; j < i - cnt; ++j) new_ans += ans[j]; new_ans += "," + to_string(cnt / len + 1) + "]"; for(int j = ans.size() - cnt % len; j < ans.size(); ++j) new_ans += ans[j]; } else{ for(int j = i - cnt - len; j < ans.size(); ++j) new_ans += ans[j]; } swap(new_ans, ans); } void optimize_1(){ string new_ans = ""; int cnt = 1; for(int i = 1; i < ans.size(); ++i){ if(ans[i] == ans[i - 1]) ++cnt; else{ if(cnt > 5) new_ans += "[" + string(1, ans[i - 1]) + "," + to_string(cnt) + "]"; else{ for(int j = 0; j < cnt; ++j) new_ans += ans[i - 1]; } cnt = 1; } } if(cnt > 5) new_ans += "[" + string(1, ans[ans.size() - 1]) + "," + to_string(cnt) + "]"; else{ for(int j = 0; j < cnt; ++j) new_ans += ans[ans.size() - 1]; } swap(new_ans, ans); } void improve(){ //posle da go napravya da pomni prez koi e minalo i da pochva ot 0 int pos = mt() % (n - 1); if(first) pos = 0; while(vis[pos] && time_left()) pos = mt() % (n - 1); if(!time_left()) return; vis[pos] = true; ull h = s[pos]; //cout << pos << endl; for(int i = pos + 1; i < n; ++i){ h *= BASE; h += s[i]; if(!time_left()) return; vector v; ull h2 = 0; int len = i - pos + 1; for(int j = 0; j < len; ++j){; h2 *= BASE; h2 += s[j]; } if(h2 == h) v.push_back(0); for(int j = len; j < n; ++j){ h2 *= BASE; h2 -= (s[j - len]) * pwr[len]; h2 += s[j]; if(h2 == h){ if(v.empty() || j - (len - 1) - v.back() >= len) v.push_back(j - (len - 1)); } } int t = v.size(); if(t == 1) break; int cand = n + 3 + len + t - len * t; int cand2 = n + 3 + (n / t + 1) + t - (n / t + 1) * t; if(cand2 >= ans.size()) break; if(cand < ans.size()){ ans = "#="; for(int j = pos; j <= i; ++j) ans += s[j]; ans += "."; int ptr = 0; for(int j = 0; j < n; ++j){ if(ptr != v.size() && v[ptr] == j){ ans += "#"; j += len - 1; ++ptr; continue; } ans += s[j]; } } } } int main(){ ios::sync_with_stdio(false); cin.tie(NULL); freopen("pattern.in", "r", stdin); freopen("pattern.out", "w", stdout); cin >> s; n = s.size(); if(n == 1){ cout << s << "\n"; return 0; } ans = s; pwr[0] = 1; for(int i = 1; i <= n; ++i) pwr[i] = pwr[i - 1] * BASE; optimize_1(); for(int i = 2; i <= 100; ++i) optimize_mult(i); while(time_left()) improve(); cout << ans << "\n"; }