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はtmp1とtmp2. 次に、次のように割り当てます。

prefixes[c1] = tmp1;

これはポインタを割り当てますが、文字列の内容をコピーしません。すべてのエントリがprefixes同じ文字列を指すことになりますtmp1. についても同様ですsuffixes。

mallocを使用しstrcpyて、新しい文字列インスタンスを作成する必要があります。

コードでは、への呼び出しをコメントアウトしましたstrcpy。これらを試してみて、実行時エラーが発生したと思われます。これらの実行時エラーは、メモリを割り当てていないことが原因でした。修正されたコードは次のようになります。

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

についても同様ですsuffixes。

本番品質のコードには、エラー チェックを含めます。そして、呼び出しが終わったらfree()、呼び出しによって返されたポインターを確実に呼び出したいと思うでしょう。malloc()

C の可変長配列、VLA の使用についても疑問があります。あなたのコードではprefixes、 、suffixes、tmp1およびtmp2はすべて VLA です。配列の次元が大きい場合、VLA を使用するとすぐにスタック オーバーフローが発生する可能性があります。私の本能は、ヒープ割り当てがここで必要なものだと言います。

于 2013-03-30T10:48:04.007 に答える