문자열 검색

문자열 검색

- 어떤 문자열 안에 다른 문자열이 들어 있는지 조사하고, 들어 있다면 그 위치를 찾아 내는 것.

브루트 포스

- 선형 검색을 확장한 알고리즘

- 이미 검사를 진행한 위치를 기억하지 못하므로 브루트- 포스의 효율법은 좋지 않다.

package basic;

import java.nio.charset.StandardCharsets;
import java.util.Scanner;

public class BFMatch {

    static int bfMatch(String txt, String pat) {
        int pt = 0; // txt커서
        int pp = 0; // pat 커서

        while (pt != txt.length() && pp != pat.length()) {
            if (txt.charAt(pt) == pat.charAt(pp)) {
                pt++;
                pp++;
            } else {
                pt = pt - pp + 1;
                pp = 0;
            }
        }

        // 검색 성공
        if (pp == pat.length())
            return pt - pp;
        return -1;

    }

    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);

        System.out.println("텍스트 : ");
        String s1 = stdIn.next(); // 텍스트용 문자열

        System.out.println("패턴 : ");
        String s2 = stdIn.next();

        int idx = bfMatch(s1, s2);

        if (idx == -1)
            System.out.println("텍스트에 패턴이 없습니다.");
        else {
            // 일치하는 문자 바로 앞까지 길이를 구함
            int len = 0;
            for (int i = 0; i < idx; i++)
                len += s1.substring(i, i + 1).getBytes().length;
            len += s2.length();


            System.out.println((idx + 1) + "번째 문자열부터 일치합니다.");
            System.out.println("텍스트 : " + s1);
            System.out.printf(String.format("패턴 : %%%ds\n", len), s2);
        }
    }
}

java.lang.String클래스는 문자열을 검색하는 indexOf메서드와 lastIndexOf메서드를 제공한다.

package basic;

public class IndexOfEx {
    public static void main(String[] args) {
        String str = "abcdefghabca";

        System.out.println(str.indexOf("a"));
        // 뒤에서부터 탐색
        System.out.println(str.lastIndexOf("a"));

        // fromIndex부터 탐색
        System.out.println(str.indexOf("a",4));
        System.out.println(str.lastIndexOf("a",6));
    }
}

KMP

- 텍스트와 패턴의 겹치는 부분을 찾아내어 검사를 다시 시작할 위치를 구하는 것

 

Boyer-Moore

- 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하며, 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 결정함

https://www.youtube.com/watch?v=mXQtunIEo0k