탐색

부르트 포스법은선형 검색을 확장한 알고리즘으로써 완전탐색으로도 불립니다. 탐색을 위해 그냥 다 때려박는 거죠.

 

package Chap08;
import java.util.Scanner;

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

        System.out.printf("텍스트: ");
        String s1 = sc.next();

        System.out.printf("패턴: ");
        String s2 = sc.next();

        int idx1 = s1.indexOf(s2);
        int idx2 = s1.lastIndexOf(s2);

        if(idx1 == -1)
            System.out.println("텍스트 안에 패턴이 없습니다.");
        else{
            int len1 = 0;
            for(int i=0; i<idx1; i++)
                len1 += s1.substring(i, i+1).getBytes().length;
            len1 += 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", len1), s2);
            System.out.println("텍스트: "+s1);
            System.out.printf(String.format("패턴:%%%ds\n", len2), s2);
        }
    }
}

indexOf메소드를 이용하여 구현했습니다.

 

 

 

KMP법은 다른 문자를 만나면 패턴을 1칸씩 옮긴 다음 다시 패턴의 처음부터 검사하는 브루트-포스법과는 다르게 중간 검사 결과를 효율적으로 사용하는 알고리즘입니다.

public class KMPmatch {
    static int KMPmatch(String txt, String pat) {
        int pt = 1;
        int pp = 0;
        int[] skip = new int[pat.length() + 1];

        skip[pt] = 0;
        while (pt != pat.length()) {
            if (pat.charAt(pt) == pat.charAt(pp))
                skip[++pt] = ++pp;
            else if (pp == 0)
                skip[++pt] = pp;
            else
                pp = skip[pp];
        }

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