fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long int;
  4. #define inf 1000000000000000LL
  5. #define mod 1000000007LL
  6. #define FOR(i,a,b) for(int i = a; i < b; i++)
  7. const ll Mod = 1'000'000'000'000'000'003LL;
  8. const ll Base = 257LL;
  9. ll mul(ll a, ll b){
  10.     __int128_t v = a;
  11.     return (v * b % Mod);
  12. }
  13. struct hashed_string{   
  14.     private:
  15.     string s; ll n;
  16.     const int N = 2000;
  17.     vector <ll> prefix;
  18.     vector <ll> pow;
  19.     public:
  20.     hashed_string(string a){
  21.         s = a; n = a.size();
  22.         prefix.assign(n, 0);
  23.         ll sum = 0;
  24.         pow.assign(n+1, 0);
  25.         pow[0] = 1;
  26.         for (int i = 1; i <= n; i++){
  27.             pow[i] = mul(pow[i-1], Base);
  28.         }
  29.         for (int i = 0; i < n; i++){
  30.             prefix[i] = (mul(sum, Base) + (s[i] == '*' ? 1 : 2)) % Mod;
  31.             sum = prefix[i];
  32.         }
  33.     }
  34.     hashed_string(){
  35.         n = 0;
  36.         pow.assign(N+1, 0);
  37.         pow[0] = 1;
  38.         for (int i = 1; i <= N; i++){
  39.             pow[i] = mul(pow[i-1], Base);
  40.         }
  41.     }
  42.     void addhash(ll a){
  43.         ll cur = a % Mod;
  44.         if (n > 0) cur = (mul(prefix.back(), Base) + cur) % Mod;
  45.         prefix.push_back(cur);
  46.         n++;
  47.     }
  48.     ll get_hash(ll l, ll r){
  49.         ll x = prefix[r];
  50.         if (l >= 1){
  51.             x = (((x - mul(prefix[l-1], pow[r - l+1]))% Mod) % Mod + Mod) % Mod;
  52.         }
  53.         return x;
  54.     }
  55. };
  56. void solve() {
  57.     ll n,m;
  58.     cin >> n >> m;
  59.     vector <string> l1(n);
  60.     vector <hashed_string> hashed_list;
  61.     FOR(i,0,n){
  62.         cin >> l1[i];
  63.     }
  64.     vector <string> l2;
  65.     for (int i = 0; i < n; i++){
  66.         l1[i] += l1[i];
  67.     }
  68.     l2 = l1;
  69.     l1.insert(l1.end(), l2.begin(), l2.end());
  70.     for (int i = 0; i < 2 * n; i++){
  71.         hashed_list.emplace_back(l1[i]);
  72.     }
  73.     vector <hashed_string> prefix(m + 1);
  74.     for (int i = 0; i < m + 1; i++){
  75.         for (int j = 0; j < 2 * n; j++){
  76.             prefix[i].addhash(hashed_list[j].get_hash(i, i + m - 1));
  77.         }
  78.     }
  79.     pair <ll,ll> pos = {-1,-1};
  80.     auto flag = [&](ll x, ll y, ll lim)->bool{
  81.         ll whole = lim / m;
  82.         if (whole >= 1){
  83.             if (prefix[y].get_hash(x, x + whole - 1) != prefix[pos.second].get_hash(pos.first, pos.first + whole - 1)){
  84.                 return false;
  85.             }
  86.         }
  87.         ll ones = lim % m;
  88.         if (ones >= 1){
  89.             if(hashed_list[x + whole].get_hash(y, y + ones - 1) != hashed_list[pos.first + whole].get_hash(pos.second, pos.second + ones - 1)){
  90.                 return false;
  91.             }
  92.         }
  93.         return true;
  94.     };
  95.     auto getchar = [&](ll x, ll y, ll val){
  96.         ll whole = val / m; ll ones = val % m;
  97.         if (ones == 0){
  98.             return l1[x + whole - 1][y + m - 1];
  99.         }
  100.         else{
  101.             return l1[x + whole][y + ones - 1];
  102.         }
  103.     };
  104.     for (int i = 0; i < n + 1; i++){
  105.         for (int j = 0; j < m + 1; j++){
  106.             if (i == 0 && j == 0){
  107.                 pos = {i,j}; continue;
  108.             }
  109.             ll lo = 1; 
  110.             ll hi = n * m;
  111.             while (lo != hi){
  112.                 ll mid = (lo + hi+ 1) / 2;
  113.                 if (flag(i,j,mid)){
  114.                     lo = mid;
  115.                 }
  116.                 else{
  117.                     hi = mid - 1;
  118.                 }
  119.             }
  120.             if (flag(i,j,lo)){
  121.                 if (hi != n * m && getchar(i, j, lo + 1) < getchar(pos.first, pos.second, lo + 1)){
  122.                     pos = {i,j};
  123.                 }
  124.             }
  125.             else{
  126.                 if (getchar(i,j,1) < getchar(pos.first, pos.second, 1)){
  127.                     pos = {i,j};
  128.                 }
  129.             }
  130.         }
  131.     }
  132.     for (int i = pos.first; i < pos.first + n; i++){
  133.         for (int j = pos.second; j < pos.second + m; j++){
  134.             cout << l1[i][j];
  135.         }
  136.         cout << "\n";
  137.     }
  138. }
  139.  
  140. int main() {
  141.     ios::sync_with_stdio(false);
  142.     cin.tie(nullptr);
  143.  
  144.     ll t = 1;
  145.     while (t--) {
  146.         solve();
  147.     }
  148.  
  149.     return 0;
  150. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5CvjA2
language:
C++14 (clang 8.0)
created:
1 hour ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!