我需要写一个用 rabin-karp 来找字符区配的function. 网上有教怎么从一组字里面找出一组字符的代码，但是就是没有教如果字是一组但是字符有很多组的时候该怎么办。我试了就是没有思路要怎么把二维的字符写进我的function.不知道有没有人能教我。


//text 是要测试的字， k 是 字符的数量，m 是 字的长度， pattern[] 是一组 字符。

int substring(char * text, int k, int m, char* patterns[])
{
    int hp = 0; // hash value of pattern
    int t = 0; // hash value of text
    int h = 0;
    int i, j;
    int p = 1009; //prime number > 1000
    int d = 256; // random base of polynomial
    char **pat = *patterns;

    for (i = 0; i < k - 1; i++)
        h = (h*d) % p;

    //hash value of pattern and hash value of the compared text substring
    for (i = 0; i < k; i++)
    {
        for (int l = 0; l <= 200; l++)
        {
            hp = (d*p + *pat[i]) % p;
            t = (d*p + text[i]) % p;
        }
    }

    //slide pattern over text
    for (i = 0; i <= m - k; i++)
    {
        if (hp == t)
        {
            for (j = 0; j < k; j++)
            {
                if (text[i+j] != *pat[j])
                    break;
            }
            if (j == k)
                return i;
        }

        if (i < m - k)
        {
            t = (d*(t - text[i] * h) + text[i+k]) % p;

            if (t < 0)
                t = (t + p);
        }
    }
}


//需要的话这是测试代码。

int main(void)
{
    char text[100001];
    char * patterns[100];
    char patt_copy[100][101];
    int i, j, k, m;
    int answer;
    for (i = 0; i<100000; i++)
    {
        text[i] = (char)(((int) 'a') + (rand() % 4));
    }
    text[100000] = '\0';
    for (i = 1; i<100000; i++)
    {
        if (text[i - 1] == text[i])
        {
            text[i] = 'e';
        }
    }
    /* generated abcde string without repeated symbols */

#ifdef DEBUG
    printf(" Printing the first 200 characters of sample string \n");
    for (i = 0; i<200; i++)
        printf("%c", text[i]);
    printf("\n");
#endif
    /* generating patterns */
    m = rand() % 100;
    /* generate 100 copies of substrings of text */
    for (i = 0; i< 100; i++)
    {
        k = (rand() % 99900);
        for (j = 0; j< 100; j++)
        {
            patt_copy[i][j] = text[j + k];
        }
        patt_copy[i][100] = '\0';
        /* but all copies but number m get modified by a repeated character */
        if (i != m)
        {
            patt_copy[i][90] = patt_copy[i][89];
        }
        patterns[i] = &(patt_copy[i][0]);
    }
    /*finished generating problem */
    printf("finished preparing text and patterns, now execute Rabin-Karp algorithm\n"); fflush(stdout);
    answer = substring(text, 100, 100, patterns);
    if (answer == m)
        printf("PASSED TEST\n");
    else
        printf("FAILED TEST\n");
    printf("m is %d ", m);
    printf("answer is %d ", answer);
    exit(0);
}

[此贴子已经被作者于2016-12-15 10:01编辑过]

int substring(char * text, int k, int m, char* patterns[])
为节省时间，最好解释下各参数。
不要让人家去看代码才能知道，如果代码写错，人家也可能会理解错。