C 入力した文字列中に特定の文字列が含まれているかを出力したい

Question

発生している問題

キーボードから入力した文字列中に特定の文字列が含まれているかを検索するため
以下のコードを記述しましたが、
結果が出力されません。
どのように修正すれば宜しいでしょうか。

条件

Nは入力する文字列の数を表します。
Sは特定の文字列 Tは入力する文字列を表します。
文字列は順番通りでなければいけません。
入力された文字列に1文字だけ衍字が含まれている場合は有効とします。
例) 調べる文字列 "take"
入力した文字列 "mistake" valid
"mistook" invalid
"mitaike" valid

#include <stdio.h>

int main(void){
    int N,i,j,k;
    char S[11];
    char T[21];
    
    scanf("%d",&N);
    scanf(" %s",S);
    
    for(i=0;i<N;i++){
        scanf(" %s",T);
        j=0;
        k=0;
        while(S[j] != '\0'){
            while(T[k] != '\0'){
                if(T[k] == S[j]){
                   while(T[k] != S[j]){
                        k++;
                        j++;
                        if(T[k] != S[j]){
                            k++;
                            if(T[k] != S[j]){
                                k--;
                                k--;
                                j--;
                                break;
                            }
                        }
                        if(S[j+1] == '\0'){
                            printf("valid\n");
                            break;
                        }
                   }
                }
                k++;
            }
            j++;
        }
        printf("invalid\n");
    }
    return 0;
}

Comments

[jimbe]

各所に printf でマーキングを入れて, どう動いているかを確認しては如何でしょうか.

[Zuishin]

strstr を使えばいいと思います。

[kazuma-s]

目を疑うコード
if(T[k] == S[j]){
　while(T[k] != S[j]){
この while ループは絶対に実行されません。

期待する具体例を挙げてもらえませんか？
例えば N が 3 のとき、S と 3個の T にどんな文字列を与えて、結果がどう表示されてほしいかです。

[fana]

衍字が含まれ得るのはSなのかTなのか？
（文章では「特定の文字列」すなわちSだと読めるが，例ではT側であるように見える）

[gily]

>jimbeさん
printfを使用して挙動を確認したところ、2つ目の入力 fgets(S,sizeof(S),stdin);の時点でバグが発生していました。
scanfの後にfgets関数を使用するとfgets関数がscanf関数の改行を読み取る為正常に動作しないというものでした。
これからはprintfで確認してから質問するようにします。ありがとうございます。

[gily]

>Zuishinさん
strstrを使用する事も考えたのですが、調べる文字列に衍字が含まれる場合のコードの書き方が分からなかったため、このような形にしております。

[gily]

>kazuma-sさん
なぜこのループは実行されないのでしょうか？宜しければ理由をお聞かせ願えますでしょうか。

具体例としては、
特定の文字列Tが「take」
Sがそれぞれ「mistake」「mistook」「mistaike」と入力されたとすると、
「mistake」には「take」が含まれるので validを出力
「mistook」には「take」が含まれないのでinvalidを出力
「mistaike」は「i」が衍字となりますが、iを無視すると「take」と読めるので validを出力
という形です。

[gily]

>fanaさん
おっしゃる通り、衍字が含まれ得るのは入力する文字列「T」の方です。
混乱させてしまって申し訳ありません。

[kazuma-s]

T[k] と S[j] が等しい時、 if の中に入ります。そこに while があります。
T[k] と S[j] が等しいので、while の条件「T[k] と S[j] が等しくない」という条件が偽です。
したがって、while の中には絶対に入りません。

> 具体例としては、
> 特定の文字列Tが「take」
> Sがそれぞれ「mistake」「mistook」「mistaike」と入力されたとすると、

S の「mistaike」に衍字が含まれるのですか？
scanf("%s", S); は 1回、scanf("%s", T); は N回実行されますよ。
S と T が逆ですか？

[gily]

>kazuma-sさん
while文の条件について何故か逆に捉えてしまっていました。勉強し直します。
そしてSとT、また逆になっていますね・・、すいません。1文字で置き換えずに inputdata等に置き換えるようにします。

Answer 1

Compile and Execute C Online (GNU GCC v7.1.1) で作成・テストしました.
入力部は端折っています.

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

/* 衍字最大数 */
#define SUPERFLUOUS_LETTER_MAX 1
#define VALID 1
#define INVALID 0

int find(char *s, char *t) {
  int i, ii, j, c;
  for(i=0; i<=(int)strlen(t)-(int)strlen(s); i++) {
    if(t[i] == s[0]) {
      c = 0; /* 衍字カウンタ */
      for(j=0, ii=i; s[j]!='\0'; ii++) {
        if(t[ii] == s[j]) {
          j ++;
        } else if(++c > SUPERFLUOUS_LETTER_MAX) {
          break;
        }
      }
      if(c <= SUPERFLUOUS_LETTER_MAX) return VALID;
    }
  }
  return INVALID;
}
void printFind(char *s, char *t) {
  printf("S='%s', T='%s' : %s\n",
      s, t, find(s,t)?"valid":"invalid");
}
int main() {
  char *s = "take";
  printFind(s,"");
  printFind(s,"tak");
  printFind(s,"take");
  printFind(s,"takie");
  printFind(s,"taakie");
  printf("\n");
  printFind(s,"mistake");
  printFind(s,"mistook");
  printFind(s,"mitaike");
  return 0;
}

S='take', T='' : invalid
S='take', T='tak' : invalid
S='take', T='take' : valid
S='take', T='takie' : valid
S='take', T='taakie' : invalid

S='take', T='mistake' : valid
S='take', T='mistook' : invalid
S='take', T='mitaike' : valid

Comments

[gily]

ご回答頂き、ありがとうございます。
main関数部分で文字列S,Tをscanfで読み込ませることで自由入力が可能となり、期待通りの結果が出力されるようになりました。
ユーザ関数やreturn文の使い方が丁寧でとても読みやすかったので、これからのプログラミングの参考にさせて頂きます。

[jimbe]

SUPERFLUOUS_LETTER_MAX を 2 以上にすると, 内側の for ループで t[ii] が t の文字列の範囲を超える場合があると思いますので, ご注意ください.
(この辺りはテキトウにしてしまっています)

Answer 2

strstr と strncmp を使ってみました。

#include <stdio.h>   // scanf, puts
#include <string.h>  // strlen, strstr, strncmp

int main(void)
{
	int N, i, j, valid, len;
	char S[110], T[210], U[110], *p;

	if (scanf("%d", &N) != 1) return 1;
	scanf("%109s", S);

	for (i = 0; i < N; i++) {
		valid = 0;
		scanf("%209s", T);
		len = strlen(T);
		if (strstr(T, S))
			valid = 1;
		else {
			for (j = 1; S[j] != '\0'; j++) {
				U[j-1] = S[j-1];
				U[j] = '\0';
				p = strstr(T, U);
				if (p && strncmp(p + j + 1, S + j, len - j) == 0) {
					valid = 1;
					break;
				}
			}
		}
		puts(valid ? "  valid" : "  invalid");
	}
	return 0;
}

Comments

[gily]

コードを記載頂きありがとうございます。コンパイルしてテストを行った結果、大方当初私が想定していた通りの結果が出力されました。
しかしながら、衍字を見逃すかどうかの判定が、「特定の文字列+衍字」が入力し終わる前に行われている為、特定の文字列の一部(S="take"であれば"ta"等)が使用された後に「特定の文字列＋衍字」が記載されている場合(例:tataike )はinvalidとなってしまいました。
こちら、解決する方法は御座いますでしょうか。

Answer 3

許容する衍字数を引数にして判定する関数を書けたので回答します。こういうコードもあるという参考にしていただけると嬉しい。

#include <string.h>  // strlen
#include <stdbool.h> // bool, true, false

bool strCompare(char tstr[], char sstr[], int maxEnji)
{
    int tlen = strlen(tstr);
    int slen = strlen(sstr);
    int limit = tlen - slen;

    for (int tx = 0; tx <= limit; tx++) {
        int sx = 0, enji = 0;
        /*
         * tstr[tx] から始まる文字列は sstr と一致するか？
         */
        while (sx < slen && enji <= maxEnji) {
            int tpos = tx + sx + enji;  // 検査する tstr の位置
            if (tpos >= tlen) break;    // オーバーラン対策

            // sstr[sx] と一致する tstr[??] を見つけながら先へ進む
            if (tstr[tpos] == sstr[sx]) {
                ++sx;       // 一致、sstr の次の文字に移る
            } else {
                ++enji;     // 衍字、tstr の比較位置をずらす
            }
        }

        if (sx == slen)     // sstr の最後まで来たら、成功！
            return true;
    }

    return false;           // 最後まで調べたけど一致できず
}

/* こんな使い方
    if (strCompare("mistake", "take", 1) == true)
        printf("valid");
*/

こういう処理は、いつまでも main() の中でやってしまおうとするのでなく、さっさと関数化することを心がけてください。そして関数の中では判定処理だけに集中する・・・これも分割統治のひとつの考え方です。私は true/false を返すだけの関数にしました。
質問者のコードが T[21] と S[11] だったので、引数を tstr、sstr として、それぞれ tlen, slen （文字列の長さ）、tx, sx （文字配列の添字）という変数名にしましたが、センス良くありません（苦笑）、そこは勘弁してください。
ちなみに、strstr() は許容する衍字数が０の場合なので、私はまず strstr() 関数を書いてみて（いわゆる車輪の再発明）、それを元に修正することで、このコードを得ました。