백준 1786 (찾기) c++

문제

1786번: 찾기

문자열이 주어지면 다음에 입력받은 문자열이 첫번째로 주어진 문자열에 있는지 구하는 문제입니다.

 

문자열 매칭 알고리즘인 KMP 알고리즘을 활용하였습니다.

먼저 fail 함수를 만드는 코드입니다.

string s, t;
getline(cin, s);
getline(cin, t);
for (int i = 1, j = 0; i < t.size(); i++) {
    while (j > 0 && t[i] != t[j])j = fail[j - 1];
    if (t[i] == t[j])fail[i] = ++j;
}

전체 문자열이 s이고 우리가 찾고자 하는 패턴 문자열이 t 입니다.

문제에서 공백도 포함해서 문자열을 입력받으므로 C++ 문법인 getline 함수로 입력을 받아주었습니다.

4번째 줄을 보면 변수 i와 j가 함께 있습니다. i는 접미사를 가리키므로 처음에 1부터 시작합니다.

j는 접두사를 가리키는 동시에 현재 처음부터 j번째 접두사와 i번째 접미사가 얼만큼 일치하는지 알려줍니다.

5번째 줄을 보면 현재 가리키는 j번째 index 접두사와 i번째 index 접미사가 서로 일치하지 않을 때 

while문을 탈출 할때까지 현재까지 일치하는 접두사와 접미사 길이인 j를 계속해서 이전에 일치했던 길이로

감소시켜줍니다.

즉, 현재 가리키는 i번째 접미사와 j번째 접두사가 서로 일치할때 까지 j를 감소시켜주는 것입니다.

위의 캡쳐한 사진에서 보면 왼쪽의 index는 i를 가리키고 fail은 접두사와 접미사가 일치하는 길이를 나타냅니다.

index 6을 보면 현재 j는 abaabac 중에서 빨간색 a를 가리키고(j==3) i는 파란색 c(i==6)를 가리킵니다.

a와 c가 다르므로 while문을 탈출하지 못하며 j = fail[3-1] = fail[2] = 1 이 됩니다.

현재 j는 abaabac 중에서 빨간색 b를 가리키고 (j==1) i는 파란색 c (i==6)를 가리킵니다.

a와 c가 다르므로 while문을 탈출하지 못하면 j = fail[1-1] = fail[0] = 0 이 됩니다.이렇게 계속 반복되면 6번째 c와 모두 일치하지않으므로 j는 결국 0이 되고 while문을 탈출하게 됩니다.

 

6번째 줄은 현재 가리키고 있는 j번째 접두사와 i번째 접미사가 일치하면 fail[i]를 ++j하면서 

일치하는 접두사와 접미사의 길이가 늘었났다는 의미입니다.

---

vector<ll>ans;
    for (int i = 0, j = 0; i < s.size(); i++) {
        while (j > 0 && s[i] != t[j])j = fail[j - 1];
        if (s[i] == t[j]) {
            if (j == t.size() - 1) {
                ans.push_back(i - t.size() + 2);
                j = fail[j];
            }
            else j++;
        }
    }
    cout << ans.size() << '\n';
    for (ll nxt : ans)cout << nxt << '\n';

이제 본격적으로 KMP 알고리즘을 실행할 단계 입니다.

ans 벡터에다가 t문자열이 일치했을 때 s문자열에서 몇번째자리에 위치를 저장합니다.

2번째 줄을 보면 for반복문에서 i와 j가 있습니다. 

i는 s문자열의 0번째 인덱스를 가리키고 j는 t문자열의 0번째 인덱스를 가리킵니다.

KMP알고리즘의 핵심은 s의 문자열을 처음부터 차례대로 t의 문자열과 일치하는지 탐색하는데 

만약 t의 문자열과 일치하지않더라도 s문자열은 뒤로가지않고 계속해서 앞으로 전진하면서 탐색합니다.

 

3번째 줄을 보면 문자열 s의 i번째 문자와 t의 j번째 문자가 같지않다면 while문을 탈출할때 까지 

j = fail[j-1]이 됩니다.

 

4번째 줄을 보면 문자열 s의 i번째 문자와 t의 j번째 문자가 같을 때 실행합니다.

5번째 줄을 보면 문자열 t가 끝까지 갔다는 의미는 문자열 s와 모든 패턴이 일치했다는 의미입니다.

6번째 줄을 보면 ans벡터에다가 문자열 s의 몇번째 글자부터 일치했는지에 대한 정보를 저장합니다.

7번째 줄을 보면 문자열 t에서 j는 j번째 인덱스에 위치한 글자가 접두사와 일치했던 위치로 이동합니다.

예를 들어 s = abbbba, t =bb 일때 

fail[0] = 0, fail[1] = 1 입니다.

문자열 abbbba를 찾으면 j = fail[1] = 1 로 이동합니다.

위의 코드는 문자열을 중복을 허용하고 탐색합니다.

예를 들어 s = abbbba , t = bb 일때 위의 코드는 총 3개의 bb를 찾습니다.

abbbba, abbbba, abbbba  

만약 7번째 코드가 j = fail[0] 이라면 중복을 허용하지 않습니다. 즉 총 2개의 bb를 찾습니다.

abbbba, abbbba

 

9번째 줄을 보면 문자열 t가 끝까지는 못왔다는 의미이므로 문자열 t를 가리키는 j를 1칸 늘려줍니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
#define inf INT_MAX
using namespace std;
using ll = long long;
using ull = unsigned long long;
ll fail[10000001];
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    string s, t;
    getline(cin, s);
    getline(cin, t);
    for (int i = 1, j = 0; i < t.size(); i++) {
        while (j > 0 && t[i] != t[j])j = fail[j - 1];
        if (t[i] == t[j])fail[i] = ++j;
    }
    vector<ll>ans;
    for (int i = 0, j = 0; i < s.size(); i++) {
        while (j > 0 && s[i] != t[j])j = fail[j - 1];
        if (s[i] == t[j]) {
            if (j == t.size() - 1) {
                ans.push_back(i - t.size() + 2);
                j = fail[j];
            }
            else j++;
        }
    }
    cout << ans.size() << '\n';
    for (ll nxt : ans)cout << nxt << '\n';
 
    return 0;
}