브루트-포스법

문자열 검색 ?

지정된 문자열에서 특정 문자열이 포함되어 있는지? 있다면 어느 위치에 있는지를 찾아내는 것

브루트-포스법

원본 문자열을 text, 검색할 문자열을 pattern이라고 부르기로하자.

포루트 포스법은 선형 검색을 확장한 단순한 알고리즘으로 단순법, 소박법이라고도 한다.

브루트-포스법은 text에 가장 앞쪽(0번 위치)부터 시작하여 pattern과 문자단위로 비교하면서 찾아가는 도중 중간에 서로 다른 문자가 발생 시 그동안 일치했던 것 문자들은 모두 무효화되고 text에서 그 다음 위치로 이동하여 다시 비교를 시작하는 방식이다. 그렇기에 효율은 좋지 않다.

.

Do it 자료구조와 함께 배우는 알고리즘 입문

//문자열 검색 
static int bfMatch(String txt, String pat){
        int pt = 0; // 텍스트 포인트
        int pp = 0; // 패턴 포인트

        while (pt != txt.length() && pp != pat.length()){
            if(txt.charAt(pt) == pat.charAt(pp)){
                pt++;
                pp++;
            } else{
                pt = pt - pp + 1; // 텍스트 시작지점 1개 이동
                pp = 0; // 패턴 가장 앞쪽
            }
        }
        if(pp == pat.length())
            return pt - pp; //일치한 시작점 반환
        return -1; // 검색 실패
    }
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);

        System.out.print("텍스트 : ");
        String s1 = s.next();

        System.out.print("패턴 : ");
        String s2 = s.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);
            // [(%%) -> % / (%d)<-len] => printf("패  턴: %(len)s",s2)
            System.out.printf(String.format("패  턴: %%%ds\n", len),s2); 
        }
    }

---

Java String 클래스 메서드 활용

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

        System.out.print("텍스트 : ");
        String s1 = s.next();

        System.out.print("패턴 : ");
        String s2 = s.next();

        int idx1 = s1.indexOf(s2); // 첫 번째 인덱스부터 찾기
        int idx2 = s1.lastIndexOf(s2); // 마지막 인덱스에서부터 찾기

        if(idx1 == -1)
            System.out.println("텍스트 안에 패턴이 없습니다.");
        else{
            int len = 0 ;
            for(int i = 0 ; i < idx1 ; i++)
                len += s1.substring(i,i+1).getBytes().length;
            len += s2.length();

            int len2 = 0 ;
            for(int i = 0 ; i < idx2 ; i++)
                len2 += s1.substring(i,i+1).getBytes().length;
            len2 += s2.length();

            System.out.println("텍스트 : " + s1);
            System.out.printf(String.format("패 턴: %%%ds\n",len),s2);
            System.out.println("텍스트 : " + s1);
            System.out.printf(String.format("패 턴: %%%ds\n",len2),s2);
        }
    }