BF 알고리즘 과 KMP 알고리즘

문자열 의 동작 에 대해 메 인 문자열 s 에서 하위 문자열 sub 를 찾 습 니 다. pos 위치 에서 시작 하 는 첫 번 째 일치 하 는 하위 문자열 은 첫 번 째 문자 의 아래 표 시 를 되 돌려 줍 니 다.BF 알고리즘 은 다음 과 같 습 니 다. 시간 복잡 도: O (mn) 문자 가 같 을 때 j +, i + +, 다 르 지 않 을 때 j 는 0 번 아래 표 시 를 되 돌려 야 합 니 다. i 는 이전 위치 로 되 돌아 가 야 합 니 다 + 1

int BF(const char *s,const char *sub, int pos)
// s      sub， pos             ，          
{
    assert(sub != NULL);
    assert(s != NULL);
    int lens = strlen(s);
    int lensub = strlen(sub);
    if (pos<0 || pos>lens)
    {
        return -1;
    }
    int i = pos;//i pos     
    int j = 0;//j 0     
    while (i < lens && j < lensub)
    {
        if (s[i] == sub[j])//      ，   
        {
            i++;
            j++;
        }
        else//      ，i      ，j  0
        {
            i = i - j + 1;
            j = 0;
        }
    }
    if (j >= lensub)
    {
        return i - j;// j      ，    [i-j]
    }
    else
    {
        return -1;
    }
}

KMP 알고리즘: BF 알고리즘 과 달리 BF 알고리즘 에 비해 KMP 알고리즘 이 더욱 효율 적 입 니 다. 그 이 유 는 BF 알고리즘 의 시간 복잡 도 는 O (mn) M 이 메 인 문자열 의 길 이 를 대표 하고 n 은 하위 문자열 의 길 이 를 대표 하기 때 문 입 니 다.KMP 의 경우 시간 복잡 도가 O (m + n) 로 변 합 니 다.KMP 와 BF 가 유일 하 게 다른 곳 에 있 습 니 다. 메 인 문자열 의 i 는 되 돌아 가지 않 고 j 도 0 번 위치 로 이동 하지 않 습 니 다.그러나 여기 서 j 는 k 위치 로 되 돌아 가 야 하기 때문에 문자열 의 각 위치 에 대응 하 는 k 값 을 저장 하 는 next [] 배열 을 가 져 왔 습 니 다. 즉, next [j] = k 로 표시 합 니 다. 서로 다른 j 는 K 값 에 대응 합 니 다. 이 K 는 앞으로 이동 할 j 가 이동 할 위치 입 니 다.한편, K 의 값 은 이렇게 구 합 니 다. 1. 규칙: 성공 부분 과 일치 하 는 두 개의 똑 같은 진자 꼬치 (자체 포함 되 지 않 음) 를 찾 습 니 다. 하 나 는 아래 표 0 으로 시작 하고 다른 하 나 는 j - 1 로 끝 납 니 다.2. 어떤 데이터 든 next [0] = - 1;next[1] = 0;여기 서 우 리 는 아래 표 시 를 시작 하고, 말 한 몇 번 째 표 시 는 1 부터 시작한다.1. 이유: 메 인 문자열 이 – "defrdes" 하위 문자열 이: "abc" 였 을 때 처음부터 일치 하지 못 했 습 니 다.0 의 이유: 하위 문자열 이 1 번 아래 에 표시 되 어 있 을 때 0 입 니 다.next 배열 의 최적화, 즉 nextval 배열 을 어떻게 얻 는 지: 다음 과 같은 문자열 이 있 습 니 다. aaaaaaaab, 그의 next 배열 은 - 1, 0, 1, 2, 3, 4, 5, 6, 7 입 니 다. 수정 후의 배열 nextval 은 - 1, - 1, - 1, - 1, - 1, - 1, - 1, - 1, - 1, - 1, - 1, - 1, 7 입 니 다.왜 수 정 된 수조 가 나 타 났 는 지, 5 번 에서 실패했다 고 가정 하면 한 걸음 물 러 설 까요, 아니면 a 입 니까, 아니면 똑 같 습 니까? 이어서 물 러 설 까요, 아니면 a 입 니까?예: 꼬치: a b c a b c a b c a b c a a b d a b next: - 1 0 0 1, 1, 2, 0, 1, 2, 3, 5, 6, 1 nextval: - 1, 0 - 1, 0, 2, 0 - 1, 0 흑체 a 의 nextval 구법: a 의 next 는 4 이 고 4 번 아래 에 표 시 된 값 도 a 이기 때문에 nextval 은 흑체 a 의 next 값 이 아니 라 4 번 아래 에 표 시 된 a 의 next 값, 즉 1 이다.

//next  ：       。       
//           
//   0     ，    j-1     
void GetNext(int *next,const char *sub)//   next     
{
    assert(sub != NULL);
    int lensub = strlen(sub);
    next[0] = -1;
    next[1] = 0;
    int i = 2;//   
    int k = 0;//        k 
    while (i < lensub)// ：abcababcabc-1 0 0 0 1 2 1 2 3 4 5 a next       a k  -1，   b  0，   。。。
    {
        if ((k == -1) || sub[k] == sub[i - 1])//    b k             a   b ，else
        {
            next[i] = k + 1;//**      k ， k+1，      c k  -1+1=0
            i++;
            k++;
        }
        else
        {
            k = next[k];//**next[0]=-1  k，k=-1  if() 
        }
    }
}

int KMP(const char *s,const char *sub, int pos)
{
    int lens = strlen(s);
    int lensub = strlen(sub);
    int *next = (int *)malloc(sizeof(int)*(lensub+1));//  next[]          ，       1
    assert(next != NULL);
    GetNext(next,sub);//  next  ，     next  
    if (pos<0 || pos>lens)
    {
        return -1;
    }
    int i = pos;//i pos     
    int j = 0;//j 0     
    while (i < lens && j < lensub)
    {
        if ((j == -1) || s[i] == sub[j])
        {
            i++;
            j++;
        }
        else
        {  
            j = next[j];//i    ，j    next      
        }
    }
        free(next);
        if (j >= lensub)
        {
            return i - j;// j      ，    [i-j]
        }
        else
        {
            return -1;
        }
}