문자열 검색 ?
지정된 문자열에서 특정 문자열이 포함되어 있는지? 있다면 어느 위치에 있는지를 찾아내는 것
브루트-포스법
원본 문자열을 text, 검색할 문자열을 pattern이라고 부르기로하자.
포루트 포스법은 선형 검색을 확장한 단순한 알고리즘으로 단순법, 소박법이라고도 한다.
브루트-포스법은 text에 가장 앞쪽(0번 위치)부터 시작하여 pattern과 문자단위로 비교하면서 찾아가는 도중 중간에 서로 다른 문자가 발생 시 그동안 일치했던 것 문자들은 모두 무효화되고 text에서 그 다음 위치로 이동하여 다시 비교를 시작하는 방식이다. 그렇기에 효율은 좋지 않다.
.
//문자열 검색
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);
}
}