반응형

문제 출처 :


https://www.acmicpc.net/problem/2401



알고리즘 분석 :


문제 해결에 필요한 사항

1. Dynamic Programming

2. KMP


KMP를 통해 긴 문자열에 짧은 문자열이 어디에 들어 갈 수 있는지를 모두 vc에 담아둔다.


이때 vc에는 짧은 문자열이 어디서 시작하는지를 표시하는 start, 어디서 끝나느지를 표시하는 end, 크기인 size를 가지고 간다.


그 후 sort를 통해 vc를 오름차순으로 정렬하여 start 순서대로 dp를 쌓아 갈 수 있도록 만들어준다.


이제 dp를 구현할 차례인데 dp는 다음과 같다.


dp[i] :: i번째 일때 최대 길이


ㅁㅁㅁㅁㅁㅁ가 있을 때 ㅁㅁㅁㅁㅁㅁ 푸른색이 시작점, 붉은색이 끝점이라고 하자. 

이때 점화식은 dp[붉은점] = max(푸른점 이전의 모든 dp + size, 현재 dp);로 나타낼 수 있다.






소스 코드 : 


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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
 
using namespace std;
 
typedef pair<int, int> pii;
 
string s, p[502];
int dp[100004];
 
vector<pair<pii, int > > vc;
map<string, int> mp;
 
vector<int> getPi(string p)
{
    int m = (int)p.size();
    int j = 0;
 
    vector<int> pi(m, 0);
 
    for (int i = 1; i< m; i++) {
        while (j > 0 && p[i] != p[j])
            j = pi[j - 1];
        if (p[i] == p[j])
            pi[i] = ++j;
    }
    return pi;
}
vector<int> kmp(string s, string p)
{
    vector<int> ans;
    auto pi = getPi(p);
    int n = (int)s.size(), m = (int)p.size(), j = 0;
    for (int i = 0; i < n; i++) {
        while (j>0 && s[i] != p[j])
            j = pi[j - 1];
        if (s[i] == p[j]) {
            if (j == m - 1) {
                ans.push_back(i - m + 1);
                j = pi[j];
            }
            else {
                j++;
            }
        }
    }
    return ans;
}
 
int main()
{
    cin >> s;
 
    int n;
    cin >> n;
 
    int idx = 0;
    for (int i = 0; i < n; i++)
    {
        string t;
        cin >> t;
 
        if (!mp.count(t))
        {
            mp[t] = 1;
            p[idx] = t;
            idx++;
        }
    }
 
    for (int i = 0; i < idx; i++)
    {
        vector<int> ans = kmp(s, p[i]);
        int len = ans.size();
        for (int j = 0; j < len; j++)
        {
            int start = ans[j];
            int end = ans[j] + p[i].size() - 1;
            int size = p[i].size();
            vc.push_back({ {start,end},size });
        }
    }
 
    sort(vc.begin(), vc.end());
 
    for (int i = 0; i < vc.size(); i++)
    {
        int start = vc[i].first.first;
        int end = vc[i].first.second;
        int size = vc[i].second;
 
        for (int j = 0; j <= end - size + 1; j++)
            dp[end + 1] = max(dp[j] + size, dp[end + 1]);
    }
 
    int cnt = 0;
    for (int i = 0; i <= s.size(); i++)
        cnt = max(cnt, dp[i]);
 
    cout << cnt;
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형
저작자표시 비영리 변경금지

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[1236번] 성 지키기  (0) 2017.12.17
[10527번] Judging Troubles  (0) 2017.12.12
[1893번] 시저 암호  (0) 2017.12.11
[11585번] 속타는 저녁 메뉴  (0) 2017.12.11
[1495번] 기타리스트  (0) 2017.12.10

티스토리툴바