[BOJ] 백준 2195 문자열 복사 c++ (문자열)

문제 출처 : https://www.acmicpc.net/problem/2195

2195번: 문자열 복사

---

풀이

최소한의 copy를 사용해 s를 p로 만들 때, 사용 횟수를 출력하는 문제이다.

p를 반복문을 돌며 s에서 같은 부분을 찾은 후, 만약 같다면 그 뒤에도 같은지 계속 검사한다.

가장 길게 검사한 부분을 저장해 idx에 더해준다.

---

코드

#include <bits/stdc++.h>

using namespace std;

string s, p;

int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> s >> p;
    int cnt = 0;
    for(int i = 0; i < p.length();){
        int max_len = 0;
        for(int j = 0; j < s.length(); j++){
            int tmp = 0;
            while(s[j+tmp] == p[i+tmp])
                tmp++;
            max_len = max(max_len, tmp);
        }
        i += max_len;
        cnt++;
    }
    cout << cnt << '\n';
	return 0;
}