문제 링크

  • 나의 풀이

라빈카프와 이진탐색을 이용하여 푼 풀이이다. 해쉬 충돌로 인해 결국 푸는데는 실패하였다.

  • 찾은 충돌 문자열

upsnoywheogetawhvotekuucofllyjisaagqaeafuilnjiuewpkglhkzmwmmhufkunavrccllnauxwatlncxumyiklusfbccoezh

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

namespace a {
typedef long long ll;

constexpr ll a = 302;
// constexpr ll a = 29;
constexpr ll p = 1000000007;
// constexpr ll p = 10007;

int sLen;
string tmp;

int findSen(const string& s, int l) {
    unordered_map<ll, bool> chk;

    ll pow_a = 1, a_ed, hVal = 0;

    for (int i = l - 1; i >= 0; i--) {
        a_ed = pow_a;
        hVal = (hVal + s[i] * pow_a) % p;
        pow_a = (pow_a * a) % p;
    }

    chk[hVal] = 1;

    for (int i = 1; i <= sLen - l; i++) {
        hVal = (hVal - s[i - 1] * a_ed) % p;
        if (hVal < 0) {
            hVal += p;
        }
        hVal = (hVal * a) % p;
        hVal = (hVal + s[i + l - 1]) % p;
        if (l == 25) {
            cout << s.substr(i, l) << "\n";
            cout << hVal << "\n";
        }
        if (chk[hVal]) {
            if (l > tmp.size()) {
                tmp = s.substr(i, l);
                cout << "lsize : " << l << "\n";
                cout << s.substr(i, l) << "\n";
                cout << hVal << "\n";
            }
            return 1;
        } else {
            chk[hVal] = 1;
        }
    }

    return 0;
}

int solve(string s) {
    int left = 0, right = sLen, mid;

    while (left < right) {
        mid = (left + right + 1) / 2;
        if (findSen(s, mid)) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }

    return left;
}

/* int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;

    getline(cin, s);
    sLen = stoi(s);
    getline(cin, s);

    int left = 0, right = sLen, mid;

    while (left < right) {
        mid = (left + right + 1) / 2;
        if (solve(s, mid)) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }

    cout << left << "\n";
} */
}  // namespace a
  • 나의 풀이 2

Suffix Array를 이용한 Longest Common Prefix를 이용해 풀었다. 특히 Longest Common Prefix 알고리즘은 O((n))으로 바꿔어야 시간초과가 나지 않고 풀 수 있다.

LCP 알고리즘에서 rank를 Comparator의 group벡터를 가져다가 쓰면 안된다. 왜냐하면 모두 같은 문자로 이뤄진 문자열에서 group벡터의 N / 2 위치 이하(미만?)의 그룹값은 모두 같아진다. T == 1일 때 마지막 perm[n -1]가장 작은 그룹값을 갖게 된다.(group[n] = -1 이기 때문) 이후 연쇄적으로 그룹값이 커지고 중간에서 증가가 멈추게 된다.

#include <bits/stdc++.h>

using namespace std;

vector<int> suffixArray;

class Comparator {
    int t;
    const vector<int>& group;

   public:
    Comparator(const vector<int>& _group, int t) : group(_group), t(t) {}

    bool operator()(int a, int b) {
        if (group[a] != group[b]) {
            return group[a] < group[b];
        }
        return group[a + t] < group[b + t];
    }
};

vector<int> getSuffixArray(const string& s) {
    int n = s.size();
    int t = 1;
    vector<int> group(n + 1);

    for (int i = 0; i < n; i++) {
        group[i] = s[i];
    }
    group[n] = -1;

    vector<int>& perm = suffixArray;
    perm.resize(n);

    for (int i = 0; i < n; i++) {
        perm[i] = i;
    }

    while (t < n) {
        Comparator comparator2T(group, t);
        sort(perm.begin(), perm.end(), comparator2T);

        t *= 2;
        if (t >= n) {
            break;
        }

        vector<int> newGroup(n + 1);
        newGroup[n] = -1;
        newGroup[perm[0]] = 0;

        for (int i = 1; i < n; i++) {
            if (comparator2T(perm[i - 1], perm[i])) {
                newGroup[perm[i]] = newGroup[perm[i - 1]] + 1;
            } else {
                newGroup[perm[i]] = newGroup[perm[i - 1]];
            }
        }

        group = newGroup;
    }

    return perm;
}

int longestFrequent(const string& s, int i, int j) {
    int ret = 0;
    while (i < s.size() && j < s.size() && s[i] == s[j]) {
        i++;
        j++;
        ret++;
    }

    return ret;
}

vector<int> getLCP(const string& s, const vector<int>& a) {
    int n = s.size();
    vector<int> ret(n), rank(n);

    for(int i = 0; i < n; i++) {
        rank[a[i]] = i;
    }

    int len = 0;
    for (int i = 0; i < n; i++) {
        int k = rank[i];
        if (k != 0) {
            int j = a[k - 1];
            while (s[i + len] == s[j + len]) {
                len++;
            }
            ret[i] = len;
            if (len) {
                len--;
            }
        }
    }

    return ret;
}

int solve(const string& s, int n) {
    getSuffixArray(s);

    int ret = 0;
    vector<int> LCP = getLCP(s, suffixArray);
    for (int i = 0; i < n; i++) {
        ret = max(ret, LCP[i]);
    }

    return ret;
}

int main() {
    int n;
    string s;

    cin >> n;
    cin >> s;

    cout << solve(s, n) << "\n";
}

댓글남기기