8. 문자열 검색 - bloodfinger8/AlgorithmStudy GitHub Wiki
조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법.
브루트 포스 공격(brute force attack) 또는 키 전수조사(exhaustive key search), 무차별 대입 공격(無差別代入攻擊) 등으로도 부른다.
흔히 수학 문제를 원시적으로 푸는 방법인 '수 대입 노가다'의 학술적 버전이다. 주로 암호학에서 연구되는 방법이나, 다른 알고리즘 분야에서도 사용되고 있다.
package 문자열검색;
import java.util.Scanner;
public class P8_1 {
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 scan = new Scanner(System.in);
System.out.print("텍스트 : ");
String s1 = scan.next();
System.out.println("패턴 : ");
String s2 = scan.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);
}
}
}
브루트 포스 알고리즘은 모든 경우를 직접 하는 알고리즘입니다
브루트 포스 알고리즘은 시간 면에서 매우 비효율적인 알고리즘입니다.
다만 그만큼 만들기도 쉽고, 다른 알고리즘을 생각하는 출발점이 된다.
KMP법은 다른 문자를 만나면 패턴을 1칸씩 옮긴 다음 다시 패턴의 처음부터 검사하는 브루트-포스법과는 다르게 중간 검사 결과를 효율적으로 사용하는 알고리즘입니다.
하지만!!!!!
몇 번째 문자부터 다시 검색을 시작할지 패턴을 이동시킬 때마다 다시 계산해야 한다면 높은 효율을 기대할 수 없습니다.
그래서 '몇 번째 문자부터 다시 검색할지' 에 대한 값을 미리 _표_로 만들어 이 문제를 해결 한답니다.
package 문자열검색;
public class P8_3 {
public int kmpMath(String txt , String pat){
//txt 커서
int pt = 1;
//pat 커서
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; //검색 실패
}
public static void main(String[] args) {
P8_3 p = new P8_3();
System.out.println(p.kmpMath("ABCABD" , "ABCABD"));
}
}Boyer-Moore법은 브루트-포스법을 개선한 KMP법 보다 효율이 더 우수하기 때문에 실제로 문자열 검색에서 널리 사용되고 있는 방법입니다.
이 알고리즘은 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정합니다.
패턴의 뒤에서부터 비교하며 마지막 문자가 일치하면 탐색을 시작합니다.
패턴의 위치를 1칸씩 옮겨가며 문자가 같은지 비교합니다. 패턴 전체가 같을 때까지 반복합니다.
탐색 도중 일치하지 않는 패턴이 발견될 경우 패턴을 일치하지 않는 문자가 발견된 위치로 옮기고 다시 탐색을 반복합니다.
pattern에 없는 문자가 발견된다면 패턴 몇 칸을 옮기더라도 패턴과 일치하지 않습니다. 이런 경우 패턴을 한꺼번에 옮깁니다.
class BMmatch {
// Boyer-Moore법으로 문자열을 검색
static int bmMatch(String txt, String pat) {
int pt; // txt 커서
int pp; // pat 커서
int txtLen = txt.length(); // txt의 문자 개수
int patLen = pat.length(); // pat의 문자 개수
int[] skip = new int[Character.MAX_VALUE + 1]; // 건너뛰기 표
// 건너뛰기 표 만들기
for (pt = 0; pt <= Character.MAX_VALUE; pt++)
skip[pt] = patLen;
for (pt = 0; pt < patLen - 1; pt++)
skip[pat.charAt(pt)] = patLen - pt - 1; // pt == patLen - 1
// 검색
while (pt < txtLen) {
pp = patLen - 1; // pat의 끝 문자에 주목
while (txt.charAt(pt) == pat.charAt(pp)) {
if (pp == 0)
return pt; // 검색 성공
pp--;
pt--;
}
pt += (skip[txt.charAt(pt)] > patLen - pp) ? skip[txt.charAt(pt)] : patLen - pp;
}
return -1; // 검색 실패
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.print("텍스트：");
String s1 = stdIn.next(); // 텍스트용 문자열
System.out.print("패턴：");
String s2 = stdIn.next(); // 패턴용 문자열
int idx = bmMatch(s1, s2); // 문자열 s1에서 문자열 s2를 BM법으로 검색
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);
}
}
}