这是上篇kmp算法根据阮景峰博客的教程实现的。
#include#include int fun( char *str , int len );//计算字符串str的部分匹配值，存储在arry数组里void comp( char *str , int len , int arry[] ){ int i = 0 , j = 0; char tmp[ len ]; strcpy( tmp , str ); for( i = 1 ; i < len + 1 ; i++ ) { tmp[ i ] = '\0'; arry[ i - 1 ] = fun( tmp , i ); strcpy( tmp , str ); }}int fun( char *str , int len ){ int i = 0; int j = 0; int count = 0; //j是计算部分匹配的次数 for( j = 1 ; j < len ; j++ ) { for( i = 0 ; i < j ; i++ ) { if( str[ i ] != str[ len - j + i ] ) //str[i]是前缀开始的，str[ len - j + i ]是从后缀开始的 break; else { if( i == j - 1 ) { count = i + 1 > count ? i + 1 : count; //因为"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度 } } } } return count;}int kmp( char *des , char *src , int arry[] ){ int i = 0 , j = 0; int len_des = strlen( des ); while( src[ i ] ) { if( src[ i ] != des[ j ] ) { if( j == 0 ) { i += 1; } else { i = ( i - j ) + ( j - arry[ j - 1 ] ); //这句很关键，移动的字符串的子串，移动的位数是已匹配的字符数 - 对应数组的值 j = 0; } continue; } if( j == len_des - 1 ) { printf( "FIND IT , at position: %d\n" , i - j + 1 ); printf( "%s\n" , src ); for( j = 0 ; j < i - len_des + 1 ; j++ ) printf( "%c" , ' ' ); printf( "%s\n" , des ); return 0; } i++; j++; } printf("Not find it!\n"); return 1;}int main(){ char *des = "ABCDABD"; char *src = "BBC ABCDAB ABCDABCDABDE"; // char *des = "abaabcac"; // char *src = "acabaabaabcacaabc"; int arry[ strlen( des ) ]; comp( des , strlen( des ) , arry ); int i = 0; for( i = 0 ; i < strlen( des ) ; i++ ) printf( "%d\n" , arry[ i ] ); kmp( des , src , arry ); return 0;}