#include #define endl '\n' #define ll long long using namespace std; const ll BASE = 131; const ll MOD = 1e9 + 7; const int MAXN = 1e5 + 5; ll hashBig[MAXN]; int main() { freopen("pattern.in", "r", stdin); freopen("pattern.out", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); string s; cin >> s; int sz = s.size(); for(int i = 1; i <= sz; i++) hashBig[i] = (hashBig[i - 1] * BASE + (s[i - 1] - 'a')) % MOD; //for(int i = 1; i <= sz; i++) cout << hashBig[i] << " "; //cout << endl; ll power = 1; ll biggest = 0, hBig, hSz; for(int subsSz = 1; subsSz < sz; subsSz++) { power *= BASE; power %= MOD; unordered_map br; for(int i = 1; i <= sz - subsSz + 1; i++) { ll h1 = hashBig[i + subsSz - 1] - power * hashBig[i - 1]; h1 %= MOD; if(h1 < 0) h1 += MOD; //cout << subsSz << " " << h1 << endl; br[h1]++; } bool change = false; for(pair p: br) { if(p.second > biggest) { biggest = p.second; hBig = p.first; hSz = subsSz; change = true; } else if(p.second == biggest) { hSz = subsSz; hBig = p.first; change = true; } } if(!change) break; } for(int i = 1; i <= hSz; i++) power = (power * BASE) % MOD; string t; for(int i = 1; i <= sz - hSz + 1; i++) { ll h1 = hashBig[i + hSz - 1] - power * hashBig[i - 1]; h1 %= MOD; if(h1 < 0) h1 += MOD; if(h1 == hBig) { t = s.substr(i - 1, hSz); break; } } //cout << t << endl; string c = "", c2; for(int i = 1; true ; i++) { c2 = c + t; if(s.find(c2) == -1) break; c += t; } string q = ""; for(int i = 0; i < c.size() - 1; i++) q += s[i]; vector indexes; for(int i = c.size() - 1; i < sz; i++) { q += s[i]; //cout << q << endl; if(q == c) indexes.push_back(i); q.erase(0, 1); } //cout << indexes.size() << endl; if(indexes.size() == 1) { int br = c.size() / t.size(); cout << '[' << t << ',' << br << ']'; if(c.size() != s.size()) cout << s.back(); cout << endl; return 0; } cout << "[[" << t << "," << c.size() / t.size() << "]"; if(indexes.size() == 2) { for(int i = indexes[0] + 1; i < indexes[1]; i++) cout << s[i]; cout << endl; return 0; } cout << "?" << "("; vector symbols; bool meet[26] = {}; for(int i = 0; i < indexes.size(); i++) { char c = s[indexes[i] + 1]; if(meet[(c - 'a')]) continue; meet[(c - 'a')] = true; symbols.push_back(c); } cout << symbols[0]; for(int i = 1; i < symbols.size(); i++) cout << "," << symbols[i]; cout << ")" << "," << indexes.size() << "]" << endl; return 0; }