가장 긴 문자열

백준 3033번: 가장 긴 문자열

아이디어

문자열 해싱. ABCED - > 2^4A + 2^3B + 2^2C + 2^1D + 2^0*E
부분 문자열마다 계속 해쉬값을 구하지 않고, 이전에 구한 값을 재활용해서 구할 수 있다.

코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MOD = 100003;
const int MAX = 200000;
int pow2[MAX+1];

int hashing(const char* c, int sz) {
    int ret = 0;
    for (int i = 0; i < sz; i++) {
        ret *= 2;
        ret %= MOD;
        ret += *(c+i);
    }
    return ret % MOD;
}

bool cmp(const char* i, const char* j, int sz) {
    bool flag = true;
    for (int k = 0; k < sz; k++) {
        if (*(i+k) != *(j+k)) {
            flag = false;
            break;
        }
    }
    return flag;
}

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

    int n;
    cin >> n;
    string s;
    cin >> s;

    pow2[0] = 1;
    for (int i = 1; i < n; i++) {
        pow2[i] = pow2[i-1]*2%MOD;
    }

    int ans = 0;
    int lo = 1, hi = n-1;
    while (lo <= hi) {
        bool found = false;
        vector<int> table[100003];
        int sz = (lo + hi)/2;
        int h = hashing(&s[0], sz);

        for (int i = 0; i <= n-sz; i++) {
            if (found) break;
            if (i != 0) {
                h = (h - s[i-1]*pow2[sz-1]%MOD + MOD)*2%MOD;
                h = (h + s[i+sz-1])%MOD;
            }
            if (table[h].size() > 0) {
                for (int pos : table[h]) {
                    if (cmp(&s[i], &s[pos], sz)) {
                        found = true;
                        ans = max(ans, sz);
                        break;
                    }
                }
            }
            table[h].push_back(i);
        }
        if (found) lo = sz+1;
        else hi = sz-1;
    }

    cout << ans;

    return 0;
}

여담

개어렵다.. 해쉬값을 인덱스로 가지는 부분 문자열의 시작 지점을 모두 저장해놓고, 비교한다.

MOD 두개써서 충돌 피하는 다른 풀이. 맨 앞에서 시작하는 부분 문자열의 해쉬값도 미리 구해놓는다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAX = 200000;
const int MUL = 31;
const ll MOD[2] = {(ll)1e8+7, (ll)1e9+9};
ll power[MAX+1][2];
ll psum[MAX+1][2];

int n;
string s;

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

    cin >> n >> s;

    power[0][0] = power[0][1] = 1;
    psum[0][0] = psum[0][1] = s[0];

    for (int i = 1; i <= n; i++) {
        for (int k = 0; k < 2; k++) {
            power[i][k] = power[i-1][k]*MUL%MOD[k];
            psum[i][k] = (psum[i-1][k]*MUL+s[i])%MOD[k];
        }
    }

    int lo = 1, hi = n-1, mid;
    unordered_set<ll> us;
    int ans = 0;
    while (lo <= hi) {
        us.clear();
        bool found = false;
        mid = (lo + hi)/2;
        ll h0 = psum[mid-1][0];
        ll h1 = psum[mid-1][1];
        us.insert(h0<<32|h1);
        for (int i = 1; i <= n-mid; i++) {
            h0 = (h0 - s[i-1]*power[mid-1][0]%MOD[0]+MOD[0]);
            h0 = (h0*MUL+s[i+mid-1])%MOD[0];
            h1 = (h1 - s[i-1]*power[mid-1][1]%MOD[1]+MOD[1]);
            h1 = (h1*MUL+s[i+mid-1])%MOD[1];

            ll key = h0<<32|h1;
            if (us.find(key) == us.end()) us.insert(key);
            else {
                found = true;
                ans = max(ans, mid);
                break;
            }
        }
        if (found) lo = mid+1;
        else hi = mid-1;
    }

    cout << ans;

    return 0;
}