Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <memory.h>
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <string>
- #include <map>
- #include <algorithm>
- #include <set>
- #include <map>
- #include <cassert>
- #include <ctime>
- #include <cstdlib>
- #include <queue>
- using namespace std;
- typedef long long ll;
- const int maxn = 256;
- string s;
- int n;
- char dp[maxn][maxn];
- char _can[maxn];
- char *can = _can + 1;
- bool solve(int start, int len) {
- memset(dp, 0, sizeof(dp));
- for (int i = 0; i + len <= n; i++) {
- bool ok = 1;
- for (int j = 0; j < len; j++) ok &= s[i + j] == s[start + j];
- if (ok) dp[i][i + len - 1] = 1;
- }
- for (int i = n - 1; i >= 0; i--) {
- for (int j = -1; j < n; j++) can[j] = 0;
- can[i - 1] = 1;
- for (int j = i; j < n; j++) {
- if (s[j] == s[(j - i) % len + start]) {
- can[j] |= can[j - 1];
- }
- for (int k = j - len; k >= i - 1; k -= len) {
- can[j] |= can[k] && dp[k + 1][j];
- }
- if ((j - i + 1) % len == 0) {
- dp[i][j] = can[j];
- }
- }
- }
- return dp[0][n - 1];
- }
- int main() {
- freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- cin >> s;
- /*for (int i = 0; i < 192; i++) s += 'a';
- vector<int> p(192);
- for (int i = 0; i < 192; i++) p[i] = i;
- random_shuffle(p.begin(), p.end());
- for (int i = 0; i < 192 / 2; i++) s[p[i]] = 'b';*/
- n = s.length();
- vector<int> cnt(26);
- for (int i = 0; i < n; i++) cnt[s[i] - 'a']++;
- for (int len = 1; len <= n; len++) if (n % len == 0) {
- set<string> st;
- for (int i = 0; i + len <= n; i++) {
- string cur = "";
- bool ok = 1;
- ok &= s[i] == s[0] && s[i + len - 1] == s[n - 1];
- vector<int> ccnt(26);
- for (int j = 0; j < len; j++) ccnt[s[i + j] - 'a']++;
- for (int j = 0; j < len; j++) cur += s[i + j];
- for (int j = 0; j < 26; j++) ok &= ccnt[j] * (n / len) == cnt[j];
- ok &= st.find(cur) == st.end();
- if (ok) {
- st.insert(cur);
- if (solve(i, len)) {
- for (int j = 0; j < len; j++) cout << s[i + j];
- cout << endl;
- return 0;
- }
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment