code c++ hoặc python

Thuật toán

Ta sẽ sử dụng tìm kiếm nhị phân + bảng băm cho bài này.

Dễ thấy, nếu khối chọn ban đầu có $x$ chữ số thỏa mãn tồn tại một khối chọn khác gồm $x$ chữ số bắt đầu từ chữ số thứ $i$ bằng khối chọn ban đầu ($i > x$) thì cũng khối chọn ban đầu có $x-1$ chữ số cũng thỏa mãn điều tương tự (khối chọn khác lúc này vẫn bắt đầu ở vị trí $i$). 

Do đó, ta sẽ chặt nhị phân theo độ dài của khối chọn.

Để kiểm tra xem hai khối chọn có bằng nhau không, ta có thể sử dụng bảng băm (hashing) để xử lý nhanh chóng.

Code (C++)

#include <bits/stdc++.h>
using namespace std;
const long long maxn = 1e7+5, base=17, mod=1e9+7;

string s;
long long n,hs[maxn],pw[maxn],l,r,mid,hs1;

long long getHash(long long i, long long j){
    return (hs[j] - hs[i-1] * pw[j-i+1] + mod*mod) % mod;
}

bool check(long long x){
    hs1 = getHash(1, x);
    for(int i=x;i<=n-x;i++){
        if(getHash(i+1, i+x) == hs1) return true;
    }
    return false;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin >> s;
    n = s.size();
    s = ' ' + s;
    pw[0] = 1;
    for(int i=1;i<=n;i++) {
        pw[i] = (pw[i-1] * base) % mod;
        hs[i] = (hs[i-1] * base + s[i] - '0' + 1) % mod;
    }
    l = 1; r = n;
    while(l <= r){
        mid = (l+r)/2;
        if(check(mid)) l = mid+1;
        else r = mid-1;
    }
    cout << r << '\n';
    if(r == 0){
        cout << 1;
        return 0;
    }
    hs1 = getHash(1, r);
    for(int i=r;i<=n-r;i++){
        if(getHash(i+1, i+r) == hs1){
            cout << i+1;break;
        }
    }
    return 0;
}