백준11590 SAVEZ

작성일 | In

문제 링크

  • http://icpc.me/11590

문제 출처

  • 2015/2016 COCI #2 4번

사용 알고리즘

  • 해싱
  • DP

풀이

문자열 $s$를 마지막 원소로 하는 가장 긴 부분 수열의 길이를 $D(s)$라고 정의합시다. $D(s)$는 $s$의 접두사이면서 접미사인 부분 문자열 $s’$에 대해 $D(s’) + 1$의 최댓값입니다.
어떤 문자열 $s$의 접두사이면서 동시에 접미사인 부분 분자열은 KMP 알고리즘의 실패 함수를 따라가면서 모두 구할 수 있습니다. 따라서 DP의 상태를 문자열이 아닌 해시값을 std::unordered_map 등을 이용해 관리하면 문제를 효율적으로 해결할 수 있습니다.

해시맵을 사용하는 경우 전체 시간 복잡도는 $O(\sum \vert S\vert)$입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll P = 917, M = 998244353;

struct Hash{
    vector<int> h, p;
    void build(const string &s){
        int n = s.size();
        h.resize(n+1); for(int i=1; i<=n; i++) h[i] = (h[i-1] * P + s[i-1]) % M;
        p.resize(n+1); p[0] = 1; for(int i=1; i<=n; i++) p[i] = p[i-1] * P % M;
    }
    int get(int l, int r){
        l++; r++;
        int res = (h[r] - 1LL * h[l-1] * p[r-l+1]) % M;
        return res >= 0 ? res : res + M;
    }
};

int N, R;
map<int,int> D;

vector<int> GetFail(const string &s){
    int n = s.size();
    vector<int> fail(n);
    for(int i=1, j=0; i<n; i++){
        while(j > 0 && s[i] != s[j]) j = fail[j-1];
        if(s[i] == s[j]) fail[i] = ++j;
    }
    return fail;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++){
        string s; cin >> s;
        Hash hash; hash.build(s);
        auto fail = GetFail(s);

        int res = 1;
        for(int j=s.size(); j>=1; j=fail[j-1]){
            int now = hash.get(0, j-1);
            auto it = D.find(now);
            if(it != D.end()) res = max(res, it->second+1);
        }
        R = max(R, res);
        D[hash.get(0, (int)s.size()-1)] = res;
    }
    cout << R;
}