1

我试图制作一个程序来计算正确的前缀和正确的后缀，然后比较集合，然后返回包含表示匹配对数的值的数组，这可以在以后的 KMP 算法中使用。但问题是前缀和后缀数组给出了错误的值。即使在新索引处添加新元素后，它也会用新元素替换数组中的所有值。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int* lps(char *,int );

int main()
{

char *pat = "abababca";

int *ptr ;
ptr = lps(pat,strlen(pat));

printf("\n***LPS***\n");


}

int * lps (char *p,int s)
{


char *prefixes[s] ;
char *suffixes[s] ;
char tmp1[s] , tmp2[s];
int i , j , k , c1 , c2 , c;

for (i = 0 ; i < s ; i ++)
{
    printf("\n\n*** --- Creating Prefixes and Suffixes for i = %d --- ***",i);

    c1 = 0 ;
    //create prefixes
    for (j = 0 ; j < i; j++)
    {
        for (k =0 ; k <= j; k++)
        {
            tmp1[k]=*(p+k);
            printf("\n *(p+%d)= %c , tmp1[%d]=%c",k,*(p+k),k,tmp1[k]);
        }

        tmp1[k]='\0';
        printf("\nprefixes[0]:%s",prefixes[0]);
        prefixes[c1] = tmp1;
        //strcpy(prefixes[c1], tmp1);

        printf("\ncurrently added %s to prefixes at %d and prefixes[%d]= %s\n ",tmp1,c1,c1,prefixes[c1]);
        c1++;
    }

    //print prefixes
    for (k = 0; k<c1; k++)
    {
        printf("\tprefixes[%d] = %s",k,prefixes[k]);
    }
    printf("\n");



    //create suffixes
    c2 = 0;
    for (j = 1 ; j <= i; j++)
    {
        for (k = j ; k  <= i; k++)
        {
            tmp2[k-j] = *((p+k));
            printf("\n *(p+%d)= %c , tmp2[%d]=%c",k,*(p+k),k-j,tmp2[k-j]);
        }

         tmp2[k-j]='\0';
         suffixes[c2] = tmp2 ;
        // strcpy(suffixes[c2], tmp2);

         printf("\ncurrently added %s to suffixes at %d and suffixes[%d]= %s\n",tmp2,c2,c2,suffixes[c2]);
        c2++;
    }

     //prinf suffixes
    for (k = 0; k<c2; k++)
    {
        printf("\tsuffixes[%d] = %s",k,suffixes[k]);
    }
    printf("\n");
    //compare the prefixes and suffixes

    c = 0 ;
    for (j = 0; j < c1; j++)
    {
        for(k=0 ; k < c2 ; k++)
        {
            printf("\nprefixes[%d] = %s , suffixes[%d] = %s\n ",j,prefixes[j],k,suffixes[k]);

            if (strcmp(prefixes[j], suffixes[k])==0)
            {
                c = c + 1 ;
            }
        }
    }

  }
  }

输出（输出的某些部分）：-

prefixes[0] = ab    prefixes[1] = ab   //it should be prefixes[0] = a   prefixes[1] = ab
4

1 回答 1

2

问题是您没有分配任何字符串。您拥有的唯一字符串lps是tmp1and tmp2。然后你做这样的分配：

prefixes[c1] = tmp1;

That assigns a pointer but does not copy the contents of the string. You'll end up with every entry in prefixes pointing to the same string, tmp1. And likewise for suffixes.

You'll need to use malloc and strcpy to make new string instances.

In the code you have commented out calls to strcpy. I suspect you tried these and encountered runtime errors. Those runtime errors were because you did not allocate any memory. The corrected code would look like:

prefixes[c1] = malloc(strlen(tmp1)+1);
strcpy(prefixes[c1], tmp1);

And similarly for suffixes.

In production quality code you'd include error checking. And you'd want to make sure that you call free() on any pointer returned by the calls malloc(), once you had finished with it.

I'd also question the use of C variable length arrays, VLAs. In your code, prefixes, suffixes, tmp1 and tmp2 are all VLAs. Using VLAs can readily lead to stack overflow if you have large array dimensions. My instincts say that heap allocation is what you need here.

于 2013-03-30T10:48:04.007 回答