지나간 삶

// 각자리의 아스키 코드에 2^0 2^1, 2^3.. 을 곱해서 해쉬값을 만들어 낸다.
hx = (hx<<1) + src[i];
hy = (hy<<1) + dest[i];

// 십진시프트를 이용한 거랑 비슷하다.
// itoa의 방식
// Sum = Sum*10 + a[i] - '0'

// 맨앞의 값만 삭제하고 다른 자리에는 2만 곱해주면 자릿수가 변경된다.
// 처음) h*2^4 + e*2^3 + l*2^2 + l*2^1 + o*2^0
// 다음) e*2^4 + l*2^3 + l*2^2 + o*2^1 + w*2^0
hy = ((hy - dest[i]*d)<<1) + dest[i+len_src];

#include <stdio.h>
#include <string.h>

#define  OUTPUT(x)  printf("index:%2d\n",(x))

void KR(char *src, int len_src, char *dest, int len_dest)
{
    int d, hx, hy, i;

    for( d=i=1; i < len_src; i++ )
        d <<= 1;

    for( hy = hx = i =0; i < len_src; i++ )
    {
        hx = (hx<<1) + src[i];
        hy = (hy<<1) + dest[i];
    }

    for( i = 0; i < len_dest-len_src; i++ )
    {
        if( hx == hy && memcmp(src, dest+i, len_src) == 0)
            OUTPUT(i);
        hy = ((hy - dest[i]*d)<<1) + dest[i+len_src];
    }
}
int main()
{
    char str[] = "acgagggaggputer";
    char search_str[] = "gagggagg";

    KR( search_str, strlen(search_str), str, strlen(str) );
    return 0;
}

- 미리 배열속에 시프트 연산을 해놓는다. PreSo( 비트별로 Or를 취해서 0이 나오면 찾는방식 )

#include <stdio.h>
#include <string.h>

#define ASIZE 256 #define  OUTPUT(x)  printf("index:%2d\n",(x))


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 *src, int len_src, char *dest, int len_dest)
{
    unsigned int lim, state;
    unsigned int S[ASIZE];
    int j;
    
    lim = preSo(src, len_src, S);    // lim = 111111100
   
    for (state = ~0, j = 0; j < len_dest; ++j)
    {
        state = (state<<1) | S[dest[j]]; 
        if (state < lim)   
            OUTPUT(j - len_src + 1);
    }
}
int main()
{
    char str[] = "acagaggaggacttcact";
    char search_str[] = "gagg";

    SO( search_str, strlen(search_str), str, strlen(str) );
    return 0;
}

1) 대상 문자열이 "sesesesesehero" ,  찾고자 하는 문자열 "sesehero" 일때 대상문자열 인덱스가 4이면 's' 인데 'h' 랑 비교했을때 틀리므로 비교를 다시 시작한다. 이때 접두, 접미를 이용하게 되는데
찾고자 하는 문자열 인덱스가 2이면 's' 인데 's'랑 다시 비교한다.

2) 결국 처음부터 다시 비교해야 하는 비용 '2'를 아끼게 된 꼴이 되므로 효율적이다.

#include <stdio.h>

void preMp( char* src, int len_src, int mpNext[] )
{
    int i, j;

    i = 0;
    j = mpNext[0] = -1;

    // 반복되는 문자를 찾아서 인덱스를 만들어준다.
    while( i < len_src )
    {
        while( j > -1 && src[i] != src[j] )
            j = mpNext[j];
        mpNext[++i] = ++j;
    }
}

void MP( char* src, int len_src, char* dest, int len_dest )
{
    int i, j, mpNext[20];
 
    preMp( src, len_src, mpNext );

    i = j = 0;

    while( j < len_dest )
    {
        // sesese를 만났을때 se~이후부터 비교를 시작한다.
        while( i > -1 && src[i] != dest[j] )
            i = mpNext[i];

        ++i;
        ++j;

        if( i >= len_src )
        {
            printf( "%d\n", j - i );
            i = mpNext[i];
        }
    }
}

int main()
{
    char y[] = "sesesesesehero";
    char x[] = "sesehero";

    MP( x, strlen(x), y, strlen(y) );
    return 0;
}

1) Morris_Pratt 알고리즘에서 PreMp 만 수정한 알고리즘. ( Knuth 할아버지.. )
 - 핵심은 접두를 접미로 밀어봐도 틀린 값이라면 틀린만큼 더 밀어준다는 개념이다.
 - 틀린 값의 비교를 절약하므로 Morris 보다도 효율적이다.

void preKmp( char *src, int len_src, int mpNext[] )
{
   int i, j;

   i = 0;
   j = mpNext[0] = -1;
   while (i < len_src)
   {
      while (j > -1 && src[i] != src[j])
         j = mpNext[j];

      i++;
      j++;

      if (src[i] == src[j])
         mpNext[i] = mpNext[j];
      else
         mpNext[i] = j;
   }
}

1) 뒤에서 부터 비교후, 틀리다면 A와 맞는곳으로 이동
2) C와 비교후 틀리다면 C까지 땡겨서 비교한다. 그후에, 끝이 G이므로 G가 나올때까지 땡긴다.

#include <stdio.h>

#define  OUTPUT(x)  printf("index:%2d\n",(x))

#define MAX(a,b)   (((a)>(b))?(a):(b))

#define ASIZE    256
#define XSIZE    256

void preBmBc(char *src, int len_src, int bmBc[])
{
    int i;

    for (i = 0; i < ASIZE; ++i)
        bmBc[i] = len_src;

    for (i = 0; i < len_src - 1; ++i)
        bmBc[src[i]] = len_src - i - 1;
}

void suffixes(char *src, int len_src, int *suff)
{
    int f, g, i;

    suff[len_src - 1] = len_src;
    g = len_src - 1;
    for (i = len_src - 2; i >= 0; --i)
    {
        if (i > g && suff[i + len_src - 1 - f] < i - g)
            suff[i] = suff[i + len_src - 1 - f];
        else
        {
            if (i < g)
                g = i;
            f = i;
            while (g >= 0 && src[g] == src[g + len_src - 1 - f])
                --g;

            suff[i] = f - g;
        }
    }
}

void preBmGs(char *src, int len_src, int bmGs[])
{
    int i, j, suff[XSIZE];

    suffixes(src, len_src, suff);

    for (i = 0; i < len_src; ++i)
        bmGs[i] = len_src;

    j = 0;

    for (i = len_src - 1; i >= 0; --i)
        if (suff[i] == i + 1)
            for (; j < len_src - 1 - i; ++j)
                if (bmGs[j] == len_src)
                    bmGs[j] = len_src - 1 - i;

    for (i = 0; i <= len_src - 2; ++i)
        bmGs[len_src - 1 - suff[i]] = len_src - 1 - i;
}


void BM(char *src, int len_src, char *dest, int len_dest)
{
    int i, j, bmGs[XSIZE], bmBc[ASIZE];

    /* Preprocessing */
    preBmGs(src, len_src, bmGs);
    preBmBc(src, len_src, bmBc);

    /* Searching */
    j = 0;
    while (j <= len_dest - len_src)
    {
        for (i = len_src - 1; i >= 0 && src[i] == dest[i + j]; --i);
        if (i < 0)
        {
            OUTPUT(j);
            j += bmGs[0];
        }
        else
            j += MAX(bmGs[i], bmBc[dest[i + j]] - len_src + 1 + i);
    }
}

int main()
{
    char y[] = "seseserahero";
    char x[] = "seserahero";

    BM( x, strlen(x), y, strlen(y) );

    return 0;
}