dvaput.cpp

Bài toán

Cho một xâu a có độ dài n. Tính xem hai xâu con (liên tiếp) mà giống nhau có độ dài đạt được lớn nhất là bao nhiêu. Hai xâu con ở đây chỉ cần có vị trí phân biệt.

Độ phức tạp

O(n logn logn)

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <vector>

#include <algorithm>

using namespace std;

#define long long long

int n;

char a[1230997];

long H[1230997];

long _2309[1230997];

bool ok(int length){

    int i; vector<long> T;

    for (i=1; i+length-1<=n; i++) T.push_back(H[i+length-1]-H[i-1]*_2309[length]);

    sort(T.begin(), T.end());

    for (i=0; i+1<T.size(); i++) if (T[i]==T[i+1]) return true;

    return false;

}

main(){

    int i;

    scanf("%d%s", &n, a+1);

    for (i=1; i<=n; i++) H[i]=H[i-1]*2309+a[i];

    _2309[0]=1;

    for (i=1; i<=n; i++) _2309[i] = _2309[i-1] * 2309;

    int ll=0, rr=n;

    i=(ll+rr)/2;

    while (ll!=i && i!=rr){

        if (ok(i)) ll=i;

        else rr=i;

        i = (ll+rr)/2;

    }

    for (i=rr; i>=ll; i--)

    if (ok(i)) { printf("%d\n",i); break; }

}

Mô tả

bool ok(int length)

kiểm tra độ dài length có thỏa mãn hay không.

Nhận xét

Chặt nhị phân kết quả. Dùng hash để so sánh các xâu con với nhau.