백준[1543] - 문서 검색

• 문제: https://www.acmicpc.net/problem/1543
• 분류: 문자열, 브루트포스
• 난이도: S5
• 소요시간: 15m
• 자아성찰:
  • 시간복잡도는 O(NM), N <=2500, M <=50으로 브루트포스를 사용할 수 있다.
  • String.substring() 메서드는 idx 매개변수가 항상 헷갈린다.. (beginIndex, endIndex)
    • substring(beginIndex) : 해당 index부터 문자열 끝까지
    • substring(beginIndex, endIndex) : beginIndex부터 endIndex - beginIndex 크기만큼

1543번: 문서 검색

 

---

public class B_1543 {

    static String s, w;
    static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        s = br.readLine();
        w = br.readLine();
        // 단어 길이가 문서 길이보다 길면 0
        if (w.length() > s.length()) {
            System.out.println(0);
            return;
        }
        int len = w.length();
        int end = w.length();
        // 문서의 끝에 도달할 때까지 반복
        while (end <= s.length()) {
            // end까지 단어 길이만큼 substring으로 슬라이싱
            String substring = s.substring(end - len, end);
            // substring이 단어와 일치한다면 count 증가 및 위치 다음 index로 이동
            if (substring.contains(w)) {
                count++;
                end = end + len;
            } else {
                end++;
            }
        }
        System.out.println(count);
    }
}