[SW Expert Academy] 1213. String
나의 풀이
String에서 특정 단어를 찾는 알고리즘은 아래와 같이 분류할 수 있다.
1. 고지식한 검색
2. 라빈카프
3. KMP
4. 보이어-무어
나는 라빈카프 방식과 KMP 방식으로 풀어보았다.
라빈카프 : 찾을 단어의 HASH 값을 이용하여 동일한 HASH 값을 갖는 단어를 찾는다. O(N)
KMP : 찾을 단어의 접두사와 접미사가 동일한 길이를 저장한 벡터를 이용하여, 탐색 범위를 줄일 수 있다. O(N+M)
나의 코드
GIthub : https://github.com/j2wooooo/Daliy_Algorithms/tree/master/Daliy_Algorithms/SW_Expert_Academy_1213
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 | // // [SW Expert Academy] 1213. String // 라빈 카프 방식으로 풀이 #include<iostream> #include<string> using namespace std; #define BASE 8 int n, ans; string sentence; string pattern; long long calchash(string s) { long long sum = 0; for (int i = 0; i < (int)pattern.size(); i++) { sum = (sum << BASE) + s[i]; } return sum; } long long findnewhash(int s, int e, int high, long long prehash) { return (prehash - (sentence[s] << (BASE*high)) << BASE) + sentence[e]; } int main(void) { int T = 10; while (T--) { cin >> n; cin >> pattern >> sentence; ans = 0; long long phash = calchash(pattern); long long shash = calchash(sentence); int psize = (int)pattern.size(); for (int i = 0; i <= (int)sentence.size() - psize; i++) { shash = findnewhash(i, i + psize, psize-1, shash); if (shash == phash) ans++; } cout << '#' << n << ' ' << ans << '\n'; } return 0; } | cs |
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 | // [SW Expert Academy] 1213. String // KMP 방식으로 코딩 #include<iostream> #include<string> #include<vector> using namespace std; int num, ans; string sentence, pattern; vector<int> makeTable() { int size = (int)pattern.size(); vector<int> table(size, 0); int j = 0; for (int i = 1; i < size; i++) { while (j != 0 && pattern[i] != pattern[j]) { j = table[j - 1]; } if (pattern[i] == pattern[j]) { table[i] = ++j; } } return table; } int kmp() { vector<int>t = makeTable(); int ssize = (int)sentence.size(); int psize = (int)pattern.size(); int ans = 0; int j = 0; for (int i = 0; i < ssize; i++) { while (j != 0 && pattern[j] != sentence[i]) { j = t[j - 1]; } if (pattern[j] == sentence[i]) { if (j == psize - 1) { ans++; j = t[j]; } else j++; } } return ans; } int main() { int T = 10; while (T--) { cin >> num; cin >> pattern; cin >> sentence; ans = kmp(); cout << '#' << num << ' ' << ans << '\n'; } return 0; } | cs |
'Problem > ETC' 카테고리의 다른 글
[SW Expert Academy] 1215. 회문1 (0) | 2019.03.06 |
---|---|
[C/C++] BOJ 5525 :: IOIOI (0) | 2019.03.05 |
[C/C++] BOJ 2163 :: 초콜릿 자르기 (0) | 2019.02.21 |
[C/C++] BOJ 1725 :: 히스토그램 (0) | 2019.01.23 |
[C/C++] BOJ 2529 :: 부등호 (0) | 2019.01.12 |