문자열(String)

NaiveMatching

Contents

두 개의 문자열이 입력으로 들어 온다. 두 번째로 들어오는 문자열이 패턴이고 첫 번째로 입력받은 문자열에서 해당 패턴을 찾는 것이 이번 문제이다. 

패턴을 찾는 방법에는 여러 방법이 있지만, 그 중에서 가장 구현하기 쉬운 방법으로 이번 문제를 해결해보자. 알고리즘은 다음과 같다. 

naiveMatching(A, P)

{

   //n is length of A, m is length of P.

   //P is pattern string.

   for i = 1 to n-m+1

      if(P[1..m] = A[i..i+m-1]) ---- (1)

      then A[i] 자리에서 매칭이 발견되었음을 알린다.

}

다른 알고리즘과 위 알고리즘을 구별하기 위해서 (1)에서 비교 횟수를 카운팅한다.

* 비교회수에 대한 내용

P[1..m]과 A[i...i+m-1]의 각각의 원소를 비교하기 위해서는 적어도 m번 비교한다. 그런데 비교 도중 중간에 일치하지 않은 문자가 있을 경우 비교를 m번까지 하지 않고 그 자리에서 바로 넘어갈 수 있다.  만일 반복 횟수 3번째에서 불일치가 발생하면 3까지만 세고 다음으로 넘어간다. 

isMatching()

{

   for m번의 반복{

      // < 이부분에서 counting 하면 된다.

      if(P[j] != A[k]) return false;

   }

   return true;

}

Input

두 개의 문자열이 들어온다. 첫 번째 문자열은 원본 문자열, 두 번째 문자열은 패턴 문자열이다. 패턴 문자열의 길이는 원본 문자열의 길이보다 작다. 원본 문자열의 최대 길이는 1000자를 넘지 않는다.

Output

비교 횟수를 출력하고 패턴 개수를 출력한다. 각 숫자는 빈 칸으로 구분 되어야 한다.

Sample Input

boboycatsoaropt

soar

Sample Output

15 1

=================================================================

Basic Rabin-Karp

Contents

한 문자열에서 패턴 문자열을 찾는 방법에 있어서 NaiveMatching에는 비효율적인 면이 없지 않아 있다. 이러한 비효율에 대해서 견딜 수 없어서 치를 떨고 있던 스티브 잡스는 곰곰히 생각을 해보았지만 도저히 수가 떠오르지 않았다. 

길거리에서 거지마냥 쭈그리고 앉아서 생각하고 있는 스티브 잡스가 안쓰러웠는지 그의 친구 라빈카프가 스티브잡스에게 다음과 같은 내용을 카톡으로 보냈다. 

Dear. 스티브 잡스

아래 내용을 적용하면 그 시간에 먹다 남긴 사과를 더 많이 만들어 낼 수 있을 것이네.. 힘내게

basicRabinKarp(A, P, d)

{

   p = 0; a_1 = 0;

   for i = 1 to m{

      p = d*p + P[i];

      a_1 = d*a_1 + A[i];

   }

   for i = 1 to n-m+1{

      // (1) --- 여기서 a를 출력한다.

      if(i != 1) then a_i = d*(a_i-1 - d^m-1*A[i-1])+A[i+m-1];

      if(p == a_i) then A[i] 자리에서 매칭이 되었음을 알린다.

   }

}

from. 우리는 영원한 과제몬

라빈 카프

스티브 잡스는 이를 보고 곰곰히 생각해보더니 유레카를 외치면서 공과대학 7호관 330호로 달려가서 잘 켜지지도 않는 쓰리스타 올인원 PC를 붙잡고 열혈 코딩을 하였다.

 

여러분이 할일은 위 알고리즘이 정확하게 돌아가는지 테스트 하는 것이다.  (1) 위치에서 a 값을 출력하고 마지막으로 발견된 패턴의 개수를 출력해보자.

Input

  입력으로 두개의 문자열이 들어온다. 첫 번재 문자열은 원본 문자열이고 두 번째 문자열은 패턴 문자열이다. 라빈 카프 알고리즘을 적용하기 위해서 들어오는 문자열의 문자는 a b c d e f g h i j 으로 총 10개로 한정한다. (10진수를 사용한다) 원본 문자열은 1000 자리를 넘지 않고, P 문자열은 15자리를 넘지 않는다.

Output

(1)의 위치에서 a를 출력하고 마지막으로 발견된 패턴의 개수를 출력한다. 각 숫자는 빈 칸으로 구분한다.

Sample Input

abcdefgabababcdefbabab

abc

Sample Output

12 12 123 234 345 456 560 601 10 101 10 101 12 123 234 345 451 510 101 10 2

=================================================================

Rabin-Karp

Contents

Basic Rabin-Karp를 구현한 소년 스티브 잡스는 특정 상황에서 해당 알고리즘이 동작하지 않는 것을 발견할 수 있었다. 디버깅을 해보니 특정 상황에서 오버플로우가 발생하는 것을 알 수 있었다. 그래서 곰곰히 생각해보니 mod 연산을 통해서 해싱을 하면 될 것 같았다. 그래서 다음과 같이 알고리즘을 구성 했다. 

RabinKarp(A, P, d, q)

{

   p = 0; b = 0;

   for i = 1 to m{

      p = (d*p + P[i]) mod q;

      b = (d*b + A[i]) mod q;

   }

   h = d^m-1 mod q;

   for i = 1 to n-m+1

      // --- (1) 여기서 b를 출력

      if(i != 1) then b_i = (d*(b_i-1 -hA[i-1]) + A[i+m-1]) mod q;

      if(p == b_i) then

         if(P[1..m] == A[i..i+m-1])

         then A[i]자리에서 매칭이 되었음을 알린다.

}

본 알고리즘을 구현하기 위해서는 %연산이 아닌 mod를 따로 구현해서 한다. (%로만 하면 안됨)

int mod(long long x, long long y){

    return (((x%y)+y)%y);

}

위 방법을 이용해서 알고리즘을 구현하는데, 입력 문자열은 [a-z](a = 0 부터 z = 25)로 26진수이고, 소수 q는 113으로 한다.

출력은 (1)에서 b를 출력하고 마지막에 패턴의 개수를 출력한다. 

Input

두 개의 문자열이 들어온다. 첫 번째 문자열은 원본 문자열, 두 번째 문자열은 패턴 문자열이다.  원본 문자열의 길이는 1000자를 넘지 않고, 패턴 문자열의 길이는 원본 문자열의 길이보다 작다.

Output

(1)에서 b를 출력하고 패턴 개수를 출력한다. 각 숫자는 빈 칸으로 구분 되어야 한다.

Sample Input

acebbceeaabceedb

eeaab

Sample Output

28 28 52 18 56 109 18 35 44 54 52 112 1

=================================================================

KMP

Contents

이번에는 KMP알고리즘을 사용해 문자열을 찾아보도록 한다.

KMP알고리즘은 각 패턴마다 비교 실패시 돌아갈 위치를 저장해 놓고 사용함으로 전처리를 위한 비용을 줄일 수 있다.

KMP알고리즘의 비교횟수를 출력하도록 한다.

- 이번 과제에서는 공백이 포함되지 않는 알파벳 소문자로 구성된 문장으로 수행한다.

KMP(A[],P[])

{

    preprocessing(P);

    i←1; // 본문 문자열 포인터

    j←1; // 패턴 문자열 포인터

 

    // n:배열 A[]의 길이, m:배열 P[]의 길이

    while(i<=n) {

        cnt++;

        if(j==0 or A[i]==P[j])

            then { i++; j++; }

        else j←π[j];

 

        if(j==m+1) then {

            //          <------- 여기서 count 값을 출력하도록 한다.

            j←π[j];

        }

    }

}

※ 위 수도코드에서 문자열 P와 A는 index 1 부터 시작한다는 가정하에 작성되었다.

Input

첫줄에는 검색할 문장(P)이 입력된다. 

둘째줄에는 찾고자하는 패턴 문장(A)이 입력된다.

Output

count값을 출력한다. count값이 여러개일 경우 라인을 갱신해가며 출력한다. 만약 검색이 실패할 경우 "fail"을 출력한다.

Sample Input

abcdabcdabcwz

abcdabcwz

 

Sample Output

14

=================================================================

Boyer-Moore

Contents

KMP를 마스터하여 자신의 블로그에 당당하게 솔루션을 기재한 스티브 잡스는 이제 패턴을 찾는 알고리즘은 더 이상 없을 것이라고 생각했다. 그러던 어느날 블로그에 스티브 잡스를 난감하게 만든 댓글이 달렸다.

Commented by : Boyer-Moore

다음 알고리즘으로 KMP보다 더 빠르게 끝낼 수 있습니다.

BoyerMooreHorspool(A, P)

{

   computeJump(P, jump);

   i = 1;

   while(i <= n-m+1){

      j = m; k = i + m - 1;

      while(j>0 and P[j] == A[k]){

         // ----(1) 여기서 카운팅 한다.

         j--;k--;

      }

      if(j == 0) then A[i] 자리에서 매칭이 발견되었음을 알린다.

      i = i + jump[A[i+m-1]];

   }

}

곰곰히 읽어보던 스티브 잡스는 발상의 전환에 무릎을 탁 치며 다시 쓰리스타 PC에 앉았다. 여러분이 할일은 성능 측정을 위해서 (1)에서 카운팅을 하고 마지막에 반복 회수와 패턴 개수를 출력하는 것이다. 

* jump를 계산하는 방법은 교과서를 참고한다.

Input

두 개의 문자열이 들어온다. 첫 번째 문자열은 원본 문자열, 두 번째 문자열은 패턴 문자열이다. 패턴 문자열의 길이는 원본 문자열의 길이보다 작다.

Output

반복 횟수를 출력하고 패턴 개수를 출력한다. 각 숫자는 빈 칸으로 구분 되어야 한다.

Sample Input

asdjfatigerdasftiger

tiger

 

Sample Output

10 2