문자열 의 고전 구현 코드 (KMP 알고리즘 구현 포함)

최근 에 데이터 구 조 를 복습 할 때 책 을 읽 을 때 대부분 가짜 코드 로 보기 힘 들 고 데이터 구 조 는 스스로 해 야 진정 으로 이해 할 수 있 습 니 다 (즉, 다른 사람의 것 을 참고 하 는 것 입 니 다). 다음은 실행 가능 한 꼬치 파일 과 KMP 구현 코드 를 제시 합 니 다.
1. 꼬치
  문자열 의 인 터 페 이 스 는 데이터 구조 책 에 이미 있 습 니 다. 다음은 String. h 입 니 다. 배열 로 이 루어 진 문자열 구조 이 고 첫 번 째 위치 에 문자열 의 길 이 를 저장 합 니 다.

/**
 *      S    T     
 * */
#include 
#include 
#include 

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 100

typedef int Status;
typedef int ElemType;

//                       String   char[MAXSIZE + 1]，    255(char   -1)
typedef char String[MAXSIZE + 1];

/**
 *      chars    T
 * */
Status StrAssign(String T, char *chars) {
    if(strlen(chars) > MAXSIZE) {
        return ERROR;
    } 
    //         
    T[0] = strlen(chars);
    for(int i = 1; i <= T[0]; i++) {
        T[i] = *(chars+i-1);
    }
    return OK;
}

/**
 *  S   T 
 * */
Status StrCopy(String T, String S) {
    for(int i = 0; i <= S[0]; i++) {
        T[i] = S[i];
    }
    return OK;
}
/**
 *          
 * */
Status StrEmpty(String S) {
    return S[0] == 0? TRUE:FALSE;
}
/**
 *      
 * */
int StrCompare(String S, String T) {
    for(int i = 1; i <= S[0] && i <= T[0]; i++) {
        if(S[i] != T[i]) {
            return S[i] - T[i];
        }
    }
    return S[0] - T[0];
}
int StrLength(String S) {
    return S[0];
}
Status ClearString(String S) {
    S[0] = 0;
    return OK;
}
/**
 *            （       MAXSIZE）  TRUE     FALSE   S2
 * */
Status StrConcat(String T, String S1, String S2) {
    if(S1[0] + S2[0] <= MAXSIZE) {
        for(int i = 1; i <= S1[0]; i++) {
            T[i] = S1[i];
        }
        for(int i = 1; i <= S2[0]; i++) {
            T[i+S1[0]] = S2[i];
        }
        T[0] = S1[0] + S2[0];
        return TRUE;
    } else {
        for(int i = 1; i <= S1[0]; i++) {
            T[i] = S1[i];
        }
        for(int i = 1; i <= MAXSIZE-S1[0]; i++) {
            T[i+S1[0]] = S2[i];
        }
        T[0] = MAXSIZE;
        return FALSE;
    }
}
/**
 *  SUb  S   pos         len   
 * */
Status SubString(String Sub, String S, int pos, int len) {
    if(pos < 1 || pos > S[0] || len < 0 || len > S[0]-pos+1) {
        return ERROR;
    }
    for(int i = 1; i <= len; i++) {
        Sub[i] = S[pos+i-1];
    }
    Sub[0] = len;
    return OK;
}
void StrPrint(String T) {
    for(int i = 1; i <= T[0]; i++) {
        printf("%c", T[i]);
    }
}
/**
 *       
 * */
int Index(String S, String T, int pos) 
{
	int i = pos;	/* i    S        ， pos  1，  pos       */
	int j = 1;				/* j    T         */
	while (i <= S[0] && j <= T[0]) /*  i  S     j  T    ，     */
	{
		if (S[i] == T[j]) 	/*          */
      	{
			++i;
         	++j; 
      	} 
      	else 				/*            */
      	{  
         	i = i-j+2;		/* i              */
         	j = 1; 			/* j     T    */
      	}      
	}
	if (j > T[0]) 
		return i-T[0];
	else 
		return 0;
}
Status StrInsert(String S, int pos, String T)
{ 
	if(pos < 1||pos > S[0]+1)
		return ERROR;
	if(S[0]+T[0] <= MAXSIZE)
	{ /*       */
		for(int i = S[0]; i >= pos; i--)
			S[i+T[0]]=S[i];
		for(int i = pos; i < pos+T[0]; i++)
			S[i]=T[i-pos+1];
		S[0]=S[0] + T[0];
		return TRUE;
	}
	else
	{ /*       */
		for(int i = MAXSIZE;i <= pos;i--)
			S[i] = S[i-T[0]];
		for(int i = pos;i < pos+T[0]; i++)
			S[i] = T[i-pos+1];
		S[0] = MAXSIZE;
		return FALSE;
	}
}
Status StrDelete(String S, int pos, int len)
{ 
	if(pos < 1||pos > S[0]-len+1||len < 0)
		return ERROR;
	for(int i = pos+len; i <= S[0]; i++)
		S[i-len] = S[i];
	S[0] -= len;
	return OK;
}
// V    S       T         
Status Replace(String S, String T, String V)
{ 
	int i = 1; /*    S          T */
	if(StrEmpty(T)) /*  T    */
		return ERROR;
	do
	{
		i=Index(S,T,i); /*    i     i       T    */
		if(i) /*   S    T */
		{
			StrDelete(S,i,StrLength(T)); /*      T */
			StrInsert(S,i,V); /*     T      V */
			i += StrLength(V); /*       V       T */
		}
	} while(i);
	return OK;
}

2. 문자열 의 일치 알고리즘
  KMP 알고리즘 에 대한 소 개 는 데이터 구조 에 있 는 책 이 상세 하 게 쓰 여 있 으 니 잘 보 셔 도 됩 니 다.다음은 문자열 의 응용 및 일치 알고리즘 코드 입 니 다. 전통 적 인 일치 알고리즘 은 String. h 에 이미 쓰 여 있 기 때문에 KMP 와 KMP 의 개선 일치 알고리즘 코드 만 있 습 니 다.

#include "String.h"
void get_next(String T, int *next) {
    int i = 1, j = 0;
    next[1] = 0;
    while(i < T[0]) {
        if(j == 0 || T[i] == T[j]) {//T[i]          T[j]         
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j]; //  
        }
    }
}
int Index_KMP(String S, String T, int pos) {
    int i = pos, j = 1, next[255];
    get_next(T, next);
    while(i <= S[0] && j <= T[0]) {
        if(j == 0 || S[i] == T[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if(j > T[0]) {
        return i - T[0];
    } else {
        return 0;
    }
}
//    T next          nextval
void get_nextval(String T, int *nextval) 
{
  	int i = 1,j = 0;
  	nextval[1]=0;
  	while (i < T[0]) 
 	{
    	if(j == 0 || T[i] == T[j]) 	/* T[i]         ，T[j]          */
		{
      		++i;  
			++j;  
			if (T[i] != T[j])      /*              */
				nextval[i] = j;	   /*     j nextval i     */
      		else 
				nextval[i] = nextval[j];	/*          ，       ，nextval    nextval i     */
    	} 
		else {
            j= nextval[j];
        }
  	}
}
//    KMP
int Index_KMP1(String S, String T, int pos) 
{
	int i = pos, j = 1, next[255];		
	get_nextval(T, next);	
	while (i <= S[0] && j <= T[0]) 
	{
		if (j == 0 || S[i] == T[j]) 
      	{
         	++i;
         	++j; 
      	} 
      	else 			
      	 	j = next[j];
	}
	if (j > T[0]) {
        return i-T[0];
    } 
	else {
        return 0;
    }
}
int main(int argc, char const **argv) {
    String S, T, S1, S2;
    char s[10] = "aaaaaaab", t[10] = "a", v[10] = "ab";
    StrAssign(S, s);
    StrAssign(S1, t);
    StrAssign(S2, v);
    StrConcat(T, S1, S2);
    StrInsert(T, 1, S1);
    printf("%d %d %d", Index(S, T, 1), Index_KMP(S, T, 1), Index_KMP1(S, T, 1));
    return 0;
}