Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- vector<vector<pair<long long,pair<int,int>>>> hashtable(30000);
- const long long Prime = 29633;
- int main()
- {
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- string st = "";
- cin>>st;
- int numberof1 = 0;
- int numberof2 = 0;
- for(int i = 0; i<st.length(); i++)
- {
- if(st[i]=='0')
- numberof2++;
- else
- numberof1++;
- }
- int lala = min(numberof1,numberof2);
- //Считали строку и определили максимально возможный в теории ответ
- int answer = 0;
- const int p = 29;
- vector<long long> p_pow (10000);
- p_pow[0] = 1;
- for (size_t i=1; i<p_pow.size(); ++i)
- p_pow[i] = p_pow[i-1] * p;
- //Как на сайте e-maxx посчитали степени для хэша
- int n = st.length();
- for(int i = 0; i<n; i++)
- {
- long long hash1 = 0;
- for(int j = i; j<min(n,i+lala); j++)
- {
- hash1 += (st[j] - '0' + 1) * p_pow[j-i];
- int u = abs((int)(hash1%Prime));
- hashtable[u].push_back(make_pair(hash1, make_pair(j-i, i)));
- //Все запихнули в хэш-таблицу (хэш, длина подстроки, индекс первого элемента)
- }
- }
- for(int i = n-1; i>=0; i--)
- {
- long long hash2 = 0;
- for(int j = i; j>=max(0, i-lala); j--)
- {
- int p = 0;
- if(st[j]=='0')
- {
- p='1';
- }
- else
- p='0';
- hash2 += (p - '0' + 1) * p_pow[i-j];
- int y = abs((int)(hash2%Prime));
- if(!hashtable[y].empty())
- {
- for(int z = 0 ; z<hashtable[y].size(); z++)
- {
- //Если хэш совпадает, подстроки не пересекаются, то пересчитываем ответ.
- if(hash2==hashtable[y][z].first&&hashtable[y][z].second.second+hashtable[y][z].second.first<j&&i-j==hashtable[y][z].second.first)
- {
- answer=max(answer, hashtable[y][z].second.first+1);
- break;
- }
- }
- }
- }
- }
- cout<<answer;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement