文字列比較のアルゴリズムについて

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
hanoha1631
記事: 5
登録日時: 2年前

文字列比較のアルゴリズムについて

#1

投稿記事 by hanoha1631 » 2年前

c言語 以下のコードについて質問です。///////////////から始まるループ部分のアルゴリズムについて誤りがあるようなのですがこれ以上間違いを見つけることができません。
指摘してくれると助かります...
//文字列を二つ読み込むaiueoとiueoa、aiueoとueoaiだったら一致と出力、aiueoとiueoのように切れていたりしたら不一致と出力する
//アルゴリズム概要
/*二つの文字列を読み込む
この時点で文字数が違うなら不一致
片方の文字列について、先頭を最後尾の後ろに回す、空いた先頭を詰めるように全体前進
これともう片方の文字列を比較、真なら一致だめなら全てのループを越え不一致を出力
*/

コード:

#include<stdio.h>
#include<string.h>//strcmp
int main(){
 int i,j,k=0,s1max;
 char s1[1000],s2[1000],s_cmp[1000];
 for(i=0;i<999;i++){//ヌル文字のスペースを取っておきます
 s1[i]='1';
 s2[i]='1';
 s_cmp[i]='1';
 }//全体を初期化します
 for(i=0;s1[i-1]!= '2';i++)scanf("%c",&s1[i]);//二つの文字列を読み込みます
 for(j=0;s2[j-1]!='2';j++)scanf("%c",&s2[j]);
 s1[i-1]='1';//ターミネーター的立ち位置の2を1にして消します
 s2[j-1]='1';
 if(i!=j-1){//二つ目の文字列を入力する際改行します。s2は改行コード分一つ多くカウントされるので調整します。
 printf("不一致\n");//この時点で文字数が違うなら不一致と表示します
 return 0;
 }
 s1max=i-1;//s1に格納された文字列の長さです
 
 for(i=0;i<1000;i++){///////////////////////////////////////////
 s1[s1max+i]=s1[i];//s1[0]を入力した文字列の後ろにある要素に代入し
 s1[i]='1';//移動した要素の跡に'1'を代入
 for(j=0;j<1000;j++){
 if(s1[j]=='1')continue;//'1'だったら無視して
 s_cmp[k]=s1[j];//'1'以外だったらs_cmp配列に代入していく
 k++;//s_cmp配列の添字をカウントしていく
 }
 if(strcmp(s_cmp,s2)==0){//もし一致したらstrcmpは0を返すので一致と出力し終了する
 printf("一致\n");
 return 0;
 }
 for(i=0;i<1000;i++)s_cmp[i]='1';//使用済み配列を初期化
 k=0;
 }
 printf("不一致\n");//以上のループを突破して来たら不一致と出力
 return 0;
}

box
記事: 2002
登録日時: 13年前

Re: 文字列比較のアルゴリズムについて

#2

投稿記事 by box » 2年前

アルゴリズムを全面的に見直したサンプルです。

コード:

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

#define N (128)

void swap(char *a, char *b)
{
    char t;

    t = *a, *a = *b, *b = t;
}

void sortData(char *s)
{
    int i, j;

    for (i = 0; i < strlen(s) - 1; i++) {
        for (j = i + 1; j < strlen(s); j++) {
            if (s[i] > s[j]) {
                swap(&s[i], &s[j]);
            }
        }
    }
}

void getData(char s[2][N])
{
    int i;

    for (i = 0; i < 2; i++) {
        printf("%dつめ>", i + 1);
        fgets(s[i], N, stdin);
        s[i][strlen(s[i]) - 1] = '\0';
        sortData(s[i]);
    }
}

int compareData(char s[2][N])
{
    return strcmp(s[0], s[1]);
}

int main(void)
{
    char str[2][N];

    getData(str);
    printf("%s一致\n", compareData(str) == 0 ? "" : "不");
    return 0;
}
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

box
記事: 2002
登録日時: 13年前

Re: 文字列比較のアルゴリズムについて

#3

投稿記事 by box » 2年前

ロジック以前の話としておかしいのは

コード:

 s1[i]='1';
 s2[i]='1';
 s_cmp[i]='1';
 for(i=0;s1[i-1]!= '2';i++)scanf("%c",&s1[i]);//二つの文字列を読み込みます
 for(j=0;s2[j-1]!='2';j++)scanf("%c",&s2[j]);
比較したい文字列に'1'や'2'を含めたいときはどうするんでしょうね?ってことです。
なので全面的に見直したコードを載せました。
aiueoとoeuiaを同一視したいのであれば、比較する前にソートすりゃいいじゃん、ってことです。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: 文字列比較のアルゴリズムについて

#4

投稿記事 by みけCAT » 2年前

boxさんのサンプルをもとに、aiueoとiueoaのようなローテートした文字列だけを一致とするようにしてみました。

1. 長さが違っていたら、不一致とする
2. 一方の文字列を2個くっつける
3. もう一方の文字列が、2個くっつけた文字列の中に入っているかを判定する

コード:

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

#define N (128)

void getData(char s[2][N])
{
    int i;

    for (i = 0; i < 2; i++) {
        printf("%dつめ>", i + 1);
        fgets(s[i], N, stdin);
        s[i][strlen(s[i]) - 1] = '\0';
    }
}

int compareData(char s[2][N])
{
    char buf[N * 2];
    if (strlen(s[0]) != strlen(s[1])) return 1;

    strcpy(buf, s[0]);
    strcat(buf, s[0]);
    return strstr(buf, s[1]) == NULL;
}

int main(void)
{
    char str[2][N];

    getData(str);
    printf("%s一致\n", compareData(str) == 0 ? "" : "不");
    return 0;
}
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: 文字列比較のアルゴリズムについて

#5

投稿記事 by みけCAT » 2年前

hanoha1631 さんが書きました:
2年前
これ以上間違いを見つけることができません。
指摘してくれると助かります...
とりあえずすぐにわかるのは

・i=0 で範囲外の s1[i-1] や、j=0で範囲外の s2[j-1] にアクセスしている
・strcmp で比較するデータに終端のナル文字を入れていない
・変数 i を用いたループの内側にまた同じ変数 i を用いたループがあるので、
 内側のループによって変数 i の値が破壊されて外側のループがうまく回らない

あたりですね。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

返信

“C言語何でも質問掲示板” へ戻る