문제 정의
- A라는 문자열 안에, B 문자열이 어디에 몇번 속해있는지 확인
문제 접근 - KMP
- B 문자열의 fail 배열를 먼저 구함
- fail 배열 : 각각의 문자가 몇번 반복되었는지 확인
- A 문자열과 fail 배열을 비교
- KMP 개념이 다소 복잡해서, 잘 설명해주신 바킹독님 블로그를 참조하시면 좋을것 같습니다.
- https://blog.encrypted.gg/857?category=773649
문제 접근 - Rabin-Karp
- 문자열의 각각의 글자를 해시값으로 변환
- 문자열의 각 위치에서 한글자씩 빼고, 더해주면서 해시값을 비교
- 해시값 구할때 a = 302, p = 1e9+7 사용
시간복잡도
- M : A 문자열의 길이
- N : B 문자열의 길이
- O(M+N)
대표예제 : 백준 1786 찾기
- KMP
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 | #include <iostream> #include <string> #include <vector> using namespace std; vector<int> fail(string& s) { vector<int> f(s.size()); int j=0; for(int i=1; i<s.size(); i++) { while(j>0 && s[j] != s[i]) j = f[j-1]; if(s[i] == s[j]) f[i] = ++j; } return f; } int main() { string T,P; getline(cin, T); getline(cin, P); vector<int> f = fail(P); int j=0; vector<int> rs; for(int i=0; i<T.size(); i++) { while(j>0 && T[i] != P[j]) j = f[j-1]; if(T[i] == P[j]) j++; if(j==P.size()) { rs.push_back(i+2-P.size()); j = f[j-1]; } } cout << rs.size() << '\n'; for(int x : rs) cout << x << '\n'; return 0; } | cs |
- Rabin-Karp
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 | #include <iostream> #include <vector> #include <string> using namespace std; typedef long long ll; ll a = 302; ll p = 1e9+7; ll powa[1000010]; int main() { string T,P; getline(cin, T); getline(cin, P); int lenT = T.size(); int lenP = P.size(); if(lenT < lenP) { cout << 0 << '\n'; return 0; } // a의 제곱값을 미리 구해놓음 powa[0] = 1; for(int i=1; i<P.size(); i++) { powa[i] = powa[i-1] * a %p; } // 각각 P길이만큼 해시값 구함 ll hashT = 0; ll hashP = 0; for(int i=0; i<P.size(); i++) { hashT = (hashT + T[i] * powa[P.size()-1-i]) %p; hashP = (hashP + P[i] * powa[P.size()-1-i]) %p; } vector<int> rs; if(hashT == hashP) rs.push_back(1); for(int i=1; i<=(T.size()-P.size()); i++) { // 앞글자 빼고, a만큼 곱해서 한자리씩 올리고, 새로 한글자 추가 hashT = (hashT - T[i-1] * powa[P.size()-1])%p; // 음수인경우 확인 if(hashT < 0) hashT += p; hashT = hashT * a % p; hashT = (hashT + T[i+P.size()-1] ) % p; if(hashT == hashP) rs.push_back(i+1); } cout << rs.size() << '\n'; for(int x : rs) cout << x << '\n'; return 0; } | cs |
'알고리즘 > 개념' 카테고리의 다른 글
[알고리즘] Dijkstra, 다익스트라 알고리즘 (0) | 2021.02.14 |
---|---|
[알고리즘] Floyd Warshall, 플로이드 와샬 알고리즘 (0) | 2021.02.08 |
[알고리즘] Minimum Spanning Tree, 최소 스패닝 트리 (0) | 2021.02.08 |
[알고리즘] 문자열 TRIE (0) | 2021.02.07 |
[알고리즘] Topological Sort, 위상정렬 (0) | 2021.02.07 |