Constraint to array dimension in C language
int KMP( const char *original, int o_len, const char *substring, int s_len ){
if( o_len < s_len )
return -1;
int k = 0;
int cur = 1;
int fail[ s_len ];
fail[ k ] = -1;
while( cur < s_len ){
k = cur - 1;
do{
if( substring[ cur ] == substring[ k ] ){
fail[ cur ] 开发者_开发问答= k;
break;
}else{
k = fail[ k ] + 1;
}
}while( k );
if( !k && ( substring[ cur ] != substring[ 0 ] ) ){
fail[ cur ] = -1;
}else if( !k ){
fail[ cur ] = 0;
}
cur++;
}
k = 0;
cur = 0;
while( ( k < s_len ) && ( cur < o_len ) ){
if( original[ cur ] == substring[ k ] ){
cur++;
k++;
}else{
if( k == 0 ){
cur++;
}else{
k = fail[ k - 1 ] + 1;
}
}
}
if( k == s_len )
return cur - k;
else
return -1;
}
This is a KMP algorithm I once coded. When I reviewed it this morning, I find it strange that an integer array is defined as int fail[ s_len ]. Does the specification requires dimesion of arrays compile-time constant? How can this code pass the compilation? By the way, my gcc version is 4.4.1. Thanks in advance!
The ability to define arrays using a variable as the dimension was added to C in C99. It's also supported as an extension by some C++ compilers, but isn't part of the C++ Standard, and won't be part of C++0x. If you are planning on portability to C89 compilers, or to C++, it's best not to use it.
To complement Neil's answer: this feature is called VLA - Variable Length Array. It was indeed added in C99 and is currently supported by several compilers. Its usage is discouraged for other reasons as well, in addition to the portability problem Neil mentioned
精彩评论