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

発生している問題

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

条件

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

C
1#include <stdio.h>
2
3int main(void){
4    int N,i,j,k;
5    char S[11];
6    char T[21];
7    
8    scanf("%d",&N);
9    scanf(" %s",S);
10    
11    for(i=0;i<N;i++){
12        scanf(" %s",T);
13        j=0;
14        k=0;
15        while(S[j] != '\0'){
16            while(T[k] != '\0'){
17                if(T[k] == S[j]){
18                   while(T[k] != S[j]){
19                        k++;
20                        j++;
21                        if(T[k] != S[j]){
22                            k++;
23                            if(T[k] != S[j]){
24                                k--;
25                                k--;
26                                j--;
27                                break;
28                            }
29                        }
30                        if(S[j+1] == '\0'){
31                            printf("valid\n");
32                            break;
33                        }
34                   }
35                }
36                k++;
37            }
38            j++;
39        }
40        printf("invalid\n");
41    }
42    return 0;
43}

jimbe

2019/11/25 08:35

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

Zuishin

2019/11/25 08:43

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

kazuma-s

2019/11/25 09:16

目を疑うコード if(T[k] == S[j]){ 　while(T[k] != S[j]){ この while ループは絶対に実行されません。期待する具体例を挙げてもらえませんか？例えば N が 3 のとき、S と 3個の T にどんな文字列を与えて、結果がどう表示されてほしいかです。

fana

2019/11/25 09:28 編集

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

gily

2019/11/25 14:55

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

gily

2019/11/25 14:58

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

gily

2019/11/25 15:09

>kazuma-sさんなぜこのループは実行されないのでしょうか？宜しければ理由をお聞かせ願えますでしょうか。具体例としては、特定の文字列Tが「take」 Sがそれぞれ「mistake」「mistook」「mistaike」と入力されたとすると、「mistake」には「take」が含まれるので validを出力「mistook」には「take」が含まれないのでinvalidを出力「mistaike」は「i」が衍字となりますが、iを無視すると「take」と読めるので validを出力という形です。

gily

2019/11/25 15:11

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

kazuma-s

2019/11/25 16:13

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

2019/11/26 00:48

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

行動規範の内容に同意します

回答3件

ベストアンサー

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

c
1#include <stdio.h>
2#include <string.h>
3
4/* 衍字最大数 */
5#define SUPERFLUOUS_LETTER_MAX 1
6#define VALID 1
7#define INVALID 0
8
9int find(char *s, char *t) {
10  int i, ii, j, c;
11  for(i=0; i<=(int)strlen(t)-(int)strlen(s); i++) {
12    if(t[i] == s[0]) {
13      c = 0; /* 衍字カウンタ */
14      for(j=0, ii=i; s[j]!='\0'; ii++) {
15        if(t[ii] == s[j]) {
16          j ++;
17        } else if(++c > SUPERFLUOUS_LETTER_MAX) {
18          break;
19        }
20      }
21      if(c <= SUPERFLUOUS_LETTER_MAX) return VALID;
22    }
23  }
24  return INVALID;
25}
26void printFind(char *s, char *t) {
27  printf("S='%s', T='%s' : %s\n",
28      s, t, find(s,t)?"valid":"invalid");
29}
30int main() {
31  char *s = "take";
32  printFind(s,"");
33  printFind(s,"tak");
34  printFind(s,"take");
35  printFind(s,"takie");
36  printFind(s,"taakie");
37  printf("\n");
38  printFind(s,"mistake");
39  printFind(s,"mistook");
40  printFind(s,"mitaike");
41  return 0;
42}

text
1S='take', T='' : invalid
2S='take', T='tak' : invalid
3S='take', T='take' : valid
4S='take', T='takie' : valid
5S='take', T='taakie' : invalid
6
7S='take', T='mistake' : valid
8S='take', T='mistook' : invalid
9S='take', T='mitaike' : valid

投稿2019/11/25 17:18

編集2019/11/26 04:09

jimbe

総合スコア12659

gily

2019/11/26 02:33

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

jimbe

2019/11/26 04:18

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

行動規範の内容に同意します

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

C
1#include <stdio.h>   // scanf, puts
2#include <string.h>  // strlen, strstr, strncmp
3
4int main(void)
5{
6	int N, i, j, valid, len;
7	char S[110], T[210], U[110], *p;
8
9	if (scanf("%d", &N) != 1) return 1;
10	scanf("%109s", S);
11
12	for (i = 0; i < N; i++) {
13		valid = 0;
14		scanf("%209s", T);
15		len = strlen(T);
16		if (strstr(T, S))
17			valid = 1;
18		else {
19			for (j = 1; S[j] != '\0'; j++) {
20				U[j-1] = S[j-1];
21				U[j] = '\0';
22				p = strstr(T, U);
23				if (p && strncmp(p + j + 1, S + j, len - j) == 0) {
24					valid = 1;
25					break;
26				}
27			}
28		}
29		puts(valid ? "  valid" : "  invalid");
30	}
31	return 0;
32}

投稿2019/11/25 16:45

kazuma-s

総合スコア8224

gily

2019/11/26 02:08

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

行動規範の内容に同意します

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

C
1#include <string.h>  // strlen
2#include <stdbool.h> // bool, true, false
3
4bool strCompare(char tstr[], char sstr[], int maxEnji)
5{
6    int tlen = strlen(tstr);
7    int slen = strlen(sstr);
8    int limit = tlen - slen;
9
10    for (int tx = 0; tx <= limit; tx++) {
11        int sx = 0, enji = 0;
12        /*
13         * tstr[tx] から始まる文字列は sstr と一致するか？
14         */
15        while (sx < slen && enji <= maxEnji) {
16            int tpos = tx + sx + enji;  // 検査する tstr の位置
17            if (tpos >= tlen) break;    // オーバーラン対策
18
19            // sstr[sx] と一致する tstr[??] を見つけながら先へ進む
20            if (tstr[tpos] == sstr[sx]) {
21                ++sx;       // 一致、sstr の次の文字に移る
22            } else {
23                ++enji;     // 衍字、tstr の比較位置をずらす
24            }
25        }
26
27        if (sx == slen)     // sstr の最後まで来たら、成功！
28            return true;
29    }
30
31    return false;           // 最後まで調べたけど一致できず
32}
33
34/* こんな使い方
35    if (strCompare("mistake", "take", 1) == true)
36        printf("valid");
37*/

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

投稿2019/11/27 09:57

編集2019/11/27 11:26