문제 85

겹치지 않게 찾기

내 상태: 미제출
난이도: 85번 문제 난이도 보기

Unranked
출제자: jinu829
시간 제한: 1000 ms
메모리 제한: 512 MB

태그 보기

문자열

문자열 $S$와 단어 $T$가 주어진다. $S$의 왼쪽부터 $T$를 찾아, 서로 겹치지 않게 나타나는 횟수를 구하라.

$S$를 왼쪽부터 차례로 살펴본다. 현재 위치에서 시작하는 문자열이 $T$와 같다면 횟수를 $1$ 늘리고, 일치한 부분의 바로 다음 글자부터 탐색을 계속한다. 같지 않다면 한 글자 오른쪽으로 이동한다.

예를 들어, $S$가 AAAA이고 $T$가 AA이면 앞의 AA와 뒤의 AA를 찾아 총 $2$번 센다. $S$가 AAA이고 $T$가 AA이면 앞의 AA를 센 뒤 글자 하나만 남으므로 총 $1$번 센다.

알파벳 대문자와 소문자는 서로 다른 글자로 취급한다.

입력

첫 번째 줄에 알파벳 대문자와 소문자, 공백으로 이루어진 문자열 $S$가 주어진다. $S$의 첫 글자와 마지막 글자는 공백이 아니다. $(1 \le \lvert S \rvert \le 100)$

두 번째 줄에 알파벳 대문자와 소문자로 이루어진 문자열 $T$가 주어진다. $(1 \le \lvert T \rvert \le 100)$

출력

첫 번째 줄에 $S$에서 $T$가 서로 겹치지 않게 나타나는 횟수를 출력한다.

예제 입력 1

abababa ABAB aba
aba

예제 출력 1

예제 입력 2

Prrogram prrogram
rr

예제 출력 2

예제 입력 3

AAAA AAA
AA

예제 출력 3

노트

예제 3에서는 AAAA에서 $2$번, 공백 뒤의 AAA에서 $1$번 찾을 수 있으므로 답은 $3$이다. $T$는 공백을 포함하지 않으므로 공백을 사이에 둔 글자들은 $T$와 일치할 수 없다.

공식 해설 풀이 스포일러 보기 접기

두 문자열의 길이가 $100$ 이하이므로 모든 가능한 시작점에서 직접 문자를 비교해도 충분하다. 겹치지 않게 세려면 일치를 찾은 뒤의 이동 거리를 달리하면 된다.

문자열의 현재 탐색 위치를 $i=0$으로 둔다. $i$부터 시작하는 $\lvert T\rvert$글자가 $T$와 같은지 직접 비교한다.

같다면 횟수를 $1$ 늘리고 $i$를 $\lvert T\rvert$만큼 옮긴다. 방금 센 구간 내부에서 시작하는 등장은 그 구간과 겹치므로 확인하지 않는다. 다르다면 $i$를 $1$만 늘려 다음 시작점을 확인한다.

남은 글자 수가 $\lvert T\rvert$보다 작아지면 탐색을 끝낸다. 공백과 대소문자를 그대로 비교하면 지문에서 정한 왼쪽부터의 탐색 과정을 정확히 따른다.

$n=\lvert S\rvert$, $m=\lvert T\rvert$라 하면 시간복잡도는 $O(nm)$, 입력 문자열을 저장하는 공간복잡도는 $O(n+m)$이다.

구현 · 언어별 풀이

C++ 구현

C++에서는 S.compare(i, T.size(), T) == 0으로 현재 구간의 일치를 확인할 수 있다. 반복은 i + T.size() <= S.size()인 동안 수행하고, 일치하면 패턴 길이만큼, 아니면 한 칸 이동한다. 공백이 있는 본문은 getline으로 읽는다.

C 구현

S는 공백을 포함하므로 fgets로 한 줄을 읽고 개행만 제거한다. 각 위치에서 T를 비교하고 일치하면 T 길이만큼, 실패하면 한 칸 이동한다. 겹치는 일치를 다시 세지 않는다.

Python 구현

공백을 보존하여 S를 읽고 S.startswith(T,i)로 검사한다. 성공 시 i += len(T), 실패 시 i += 1이다. replace나 정규식 없이 비중첩 개수를 직접 셀 수 있다.

Java 구현

S를 readLine()으로 읽고 startsWith(T,i)를 검사한다. 성공 때 T.length()만큼 건너뛰고 실패 때 한 칸 이동한다. trim()으로 문장 내용을 바꾸지 않는다.

Rust 구현

S,T를 ASCII 바이트로 보고 길이 범위 안의 슬라이스를 비교한다. 성공 시 T 길이만큼 이동한다. 공백이 있는 S는 split_whitespace() 토큰 하나로 읽지 않는다.

JavaScript 구현

본문 줄의 공백과 대소문자를 보존하고, 패턴 줄은 따로 읽는다. 최대 길이가 $100$이므로 startsWith로 각 위치를 직접 확인하면 충분하다.

let count = 0;
for (let i = 0; i + t.length <= s.length;) {
    if (s.startsWith(t, i)) {
        count++;
        i += t.length;
    } else {
        i++;
    }
}
console.log(count);

일치하면 패턴 길이만큼 이동해야 겹친 등장은 세지 않는다. 정규식의 전역·중첩 옵션이나 별도 KMP 구현은 이 제한에서 필요 없다.

제출

언어