开发者

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

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜