Advertisement
Guest User

Untitled

a guest
Dec 6th, 2012
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.25 KB | None | 0 0
  1. vector<vector<pair<long long,pair<int,int>>>> hashtable(30000);
  2. const long long Prime = 29633;
  3. int main()
  4. {  
  5.     freopen("input.txt", "r", stdin);
  6.     freopen("output.txt", "w", stdout);
  7.     string st = "";
  8.     cin>>st;
  9.     int numberof1 = 0;
  10.        int numberof2 = 0;
  11.        for(int i = 0; i<st.length(); i++)
  12.        {
  13.          if(st[i]=='0')
  14.           numberof2++;
  15.          else
  16.           numberof1++;
  17.        }
  18.  
  19.        int lala = min(numberof1,numberof2);
  20.             //Считали строку и определили максимально возможный в теории ответ
  21.     int answer = 0;
  22.     const int p = 29;
  23.     vector<long long> p_pow (10000);
  24.     p_pow[0] = 1;
  25.     for (size_t i=1; i<p_pow.size(); ++i)
  26.        p_pow[i] = p_pow[i-1] * p;
  27.             //Как на сайте e-maxx посчитали степени для хэша
  28.     int n = st.length();
  29.     for(int i = 0; i<n; i++)
  30.     {
  31.  
  32.        long long hash1 = 0;
  33.        for(int j = i; j<min(n,i+lala); j++)
  34.        {
  35.        hash1 += (st[j] - '0' + 1) * p_pow[j-i];
  36.        int u = abs((int)(hash1%Prime));
  37.        hashtable[u].push_back(make_pair(hash1, make_pair(j-i, i)));
  38.                    //Все запихнули в хэш-таблицу (хэш, длина подстроки, индекс первого элемента)
  39.        }
  40.     }
  41.  
  42.     for(int i = n-1; i>=0; i--)
  43.     {
  44.  
  45.        long long hash2 = 0;
  46.        for(int j = i; j>=max(0, i-lala); j--)
  47.        {
  48.          int p = 0;
  49.           if(st[j]=='0')
  50.           {
  51.               p='1';
  52.           }
  53.           else
  54.               p='0';
  55.  
  56.        hash2 += (p - '0' + 1) * p_pow[i-j];
  57.     int y = abs((int)(hash2%Prime));
  58.        if(!hashtable[y].empty())
  59.        {
  60.  
  61.          for(int z = 0 ; z<hashtable[y].size(); z++)
  62.          {
  63.            //Если хэш совпадает, подстроки не пересекаются, то пересчитываем ответ.
  64.  
  65.          if(hash2==hashtable[y][z].first&&hashtable[y][z].second.second+hashtable[y][z].second.first<j&&i-j==hashtable[y][z].second.first)
  66.          {
  67.           answer=max(answer, hashtable[y][z].second.first+1);
  68.           break;
  69.          }
  70.          }
  71.        }
  72.  
  73.        }
  74.     }
  75.     cout<<answer;
  76.     return 0;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement