Guest User

Untitled

a guest
Mar 29th, 2015
441
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.03 KB | None | 0 0
  1. #include <memory.h>
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <vector>
  5. #include <string>
  6. #include <map>
  7. #include <algorithm>
  8. #include <set>
  9. #include <map>
  10. #include <cassert>
  11. #include <ctime>
  12. #include <cstdlib>
  13. #include <queue>
  14.  
  15.  
  16. using namespace std;
  17.  
  18. typedef long long ll;
  19.  
  20. const int maxn = 256;
  21.  
  22. string s;
  23. int n;
  24. char dp[maxn][maxn];
  25. char _can[maxn];
  26. char *can = _can + 1;
  27.  
  28. bool solve(int start, int len) {
  29.     memset(dp, 0, sizeof(dp));
  30.  
  31.     for (int i = 0; i + len <= n; i++) {
  32.         bool ok = 1;
  33.         for (int j = 0; j < len; j++) ok &= s[i + j] == s[start + j];
  34.         if (ok) dp[i][i + len - 1] = 1;
  35.     }
  36.  
  37.     for (int i = n - 1; i >= 0; i--) {
  38.         for (int j = -1; j < n; j++) can[j] = 0;
  39.         can[i - 1] = 1;
  40.  
  41.         for (int j = i; j < n; j++) {
  42.             if (s[j] == s[(j - i) % len + start]) {
  43.                 can[j] |= can[j - 1];
  44.             }
  45.             for (int k = j - len; k >= i - 1; k -= len) {
  46.                 can[j] |= can[k] && dp[k + 1][j];
  47.             }
  48.             if ((j - i + 1) % len == 0) {
  49.                 dp[i][j] = can[j];
  50.             }
  51.         }
  52.     }
  53.     return dp[0][n - 1];
  54. }
  55.  
  56. int main() {
  57.     freopen("input.txt", "r", stdin);
  58.     //freopen("output.txt", "w", stdout);
  59.    
  60.     cin >> s;
  61.     /*for (int i = 0; i < 192; i++) s += 'a';
  62.     vector<int> p(192);
  63.     for (int i = 0; i < 192; i++) p[i] = i;
  64.     random_shuffle(p.begin(), p.end());
  65.     for (int i = 0; i < 192 / 2; i++) s[p[i]] = 'b';*/
  66.  
  67.     n = s.length();
  68.  
  69.     vector<int> cnt(26);
  70.     for (int i = 0; i < n; i++) cnt[s[i] - 'a']++;
  71.  
  72.     for (int len = 1; len <= n; len++) if (n % len == 0) {
  73.         set<string> st;
  74.         for (int i = 0; i + len <= n; i++) {
  75.             string cur = "";
  76.             bool ok = 1;
  77.             ok &= s[i] == s[0] && s[i + len - 1] == s[n - 1];
  78.             vector<int> ccnt(26);
  79.             for (int j = 0; j < len; j++) ccnt[s[i + j] - 'a']++;
  80.             for (int j = 0; j < len; j++) cur += s[i + j];
  81.             for (int j = 0; j < 26; j++) ok &= ccnt[j] * (n / len) == cnt[j];
  82.  
  83.             ok &= st.find(cur) == st.end();
  84.             if (ok) {
  85.                 st.insert(cur);
  86.                 if (solve(i, len)) {
  87.                     for (int j = 0; j < len; j++) cout << s[i + j];
  88.                     cout << endl;
  89.                     return 0;
  90.                 }
  91.             }
  92.         }
  93.     }
  94.  
  95.     return 0;
  96. }
Advertisement
Add Comment
Please, Sign In to add comment