반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. KMP


문제를 해결하기위해 첫번째 문자열인 order와 두번째 문자열인 original 세번째 문자열인 secret가 있다.


order의 크기 - 1만큼 우리는 shift를 할 수 있고, 결국 원래 문자열이 shift를 했을 때 생기는 문자열을 이용하여


kmp(secret, shift 했을 때 생기는 문자열)를 돌린다.


이때 kmp에서 하나의 match를 찾으면 shift값을 정답 벡터에 넣어준다.



마지막으로 정답 벡터가 크기가 얼마냐에 따라 답을 출력해주면 문제를 해결 할 수 있다.




소스 코드 : 


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
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
 
using namespace std;
 
typedef pair<int, int> pii;
 
string s, p[502];
map<char, 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()
{
    int tc;
    cin >> tc;
 
    while (tc--)
    {
        vector<int> ans;
        string order, ori, secret;
 
        cin >> order >> ori >> secret;
 
        int lenOrder = order.size();
        for (int i = 0; i < lenOrder; i++)
            mp[order[i]] = i;
        
        int lenOri = ori.size();
        for (int shift = 0; shift < lenOrder; shift++)
        {
            string tmp = ori;
            for (int i = 0; i < lenOri; i++)
                tmp[i] = order[(mp[tmp[i]] + shift) % lenOrder];
            //cout << "shift :: " << shift << " " << tmp << endl;
 
            vector<int> vc = kmp(secret, tmp);
 
            if (vc.size() == 1)
                ans.push_back(shift);
        }
 
        if (ans.size() == 0)
            cout << "no solution" << endl;
        else if (ans.size() == 1)
            cout << "unique: " << ans[0] << endl;
        else
        {
            cout << "ambiguous: ";
            for (int i = 0; i < ans.size(); i++)
                cout << ans[i] << " ";
            cout << endl;
        }
 
    }
    return 0;
}
 
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


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

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

[10527번] Judging Troubles  (0) 2017.12.12
[2401번] 문자열 붙여넣기  (0) 2017.12.12
[11585번] 속타는 저녁 메뉴  (0) 2017.12.11
[1495번] 기타리스트  (0) 2017.12.10
[3640번] 제독  (0) 2017.12.09

티스토리툴바