[박혜웅] Shift-Or

• Shift-Or 의 특징

• • 비트병렬성을 기반으로, 머신의 처리단위(워드) 내부에서 비트연산 이용
  • 머신의 처리 단위보다 패턴의 길이가 짧다면 효과적임

  • 성능

  • • 전처리 시간,공간복잡도: O(m + )
    • 검색시 시간복잡도: O(n)

 

• Shift-Or 기본 개념

  •  
    
    

 

 

• Shift-Or 설명

  • bit-mask table

    • 가로: 패턴
    • 세로: 패턴에 나타나는 문자종류
    • 패턴에 해당하는 문자가 나타나는 곳만 0으로 세팅.
    •  
      

 

 

• Shift-Or 실행
•     

 

• Shift-Or 소스

1. int preSo(char *x, int m, unsigned int S[]) {
       unsigned int j, lim;
       int i;
       for (i = 0; i < ASIZE; ++i)
         S[i] = ~0;
       for (lim = i = 0, j = 1; i < m; ++i, j <<= 1) {
         S[x[i]] &= ~j;
         lim |= j;
       }
       lim = ~(lim>>1);
       return(lim);
     }
   
     void SO(char *x, int m, char *y, int n) {
       unsigned int lim, state;
       unsigned int S[ASIZE];
       int j;
       if (m > WORD)
         error("SO: Use pattern size <= word size");
   
       /* Preprocessing */
       lim = preSo(x, m, S);
   
       /* Searching */
       for (state = ~0, j = 0; j < n; ++j) {
         state = (state<<1) | S[y[j]];
         if (state < lim)
           OUTPUT(j - m + 1);
       }
     }