2
getchar（）を使用して、長い文字列で2つのパターン（RFMKCRやAWYなど）を検索するにはどうすればよいですか？配列のない長いシーケンスでパターン文字列を検索する
P.Sアレイを使用することはできません。 ありがとう！
A
答えて
2
これは、汎用機能getchar1()から入力を受け取るの状態マシンの完全なコードです。パターン：AWYおよびRFMKCRが認識され、報告されます。
ファンクションgetchar1()は、入力から文字を取得する関数の単なるラッパーです。 getchar()またはscanfを内部で使用できます。 STOPで定義されたCharは、入力処理を終了します。
この問題の難点は、2つのパターン：AWYとRFMKCRの2つのパターンの開始を同時に探す必要があることにあります。私たちは、別のパターンの途中で違うパターンを探すか、再同期するように強制的に切り替えることがあります。
3つの完全な解が与えられる。
最初の解法再帰。
第2の解決策は、再帰呼び出しを避ける単純なgoto構造を使用します。このアプローチは、この特定の問題に対して非常にうまく機能します。
注：gotoの利用が一般的に可能な限りgotoに優先してbreak、continue、およびreturnステートメントを使用するのは良いプログラミングスタイルであるC. に落胆しています。 breakステートメントはループの1つのレベルからのみ終了するため、深くネストされたループ内からループを終了するには、gotoが必要な場合があります。
第3の解決策は、再帰またはgotoステートメントを使用せず、異なるパターンに容易に適合させることができる一般的なアプローチを示すことを試みる。
溶液1）
#include <stdio.h>
#include <stdlib.h>
#define STOP '!'
int START(void);
int AWY(void);
int RFMKCR(void);
int END(void);
int getchar1 (void)
{
char in;
in = getchar(); // scanf ("%c", &in);
return in;
}
int START(void)
{
int c = getchar1();
if (c == 'A') return AWY();
if (c == 'R') return RFMKCR();
if (c == STOP) return END();
return 1;
}
int AWY(void) // A already found
{
int c = getchar1();
if (c == 'A') return AWY();
if (c == 'R') return RFMKCR();
if (c == STOP) return END();
if (c != 'W') return 1;
// W found
c = getchar1();
if (c == 'A') return AWY();
if (c == 'R') return RFMKCR();
if (c == STOP) return END();
if (c != 'Y') return 1;
// Y found
printf ("AWY found\n");
return 1;
}
int RFMKCR(void) // R already found
{
int c = getchar1();
if (c == 'A') return AWY();
if (c == 'R') return RFMKCR();
if (c == STOP) return END();
if (c != 'F') return 1;
// F found
c = getchar1();
if (c == 'A') return AWY();
if (c == 'R') return RFMKCR();
if (c == STOP) return END();
if (c != 'M') return 1;
// M found
c = getchar1();
if (c == 'A') return AWY();
if (c == 'R') return RFMKCR();
if (c == STOP) return END();
if (c != 'K') return 1;
// K found
c = getchar1();
if (c == 'A') return AWY();
if (c == 'R') return RFMKCR();
if (c == STOP) return END();
if (c != 'C') return 1;
// C found
c = getchar1();
if (c == 'A') return AWY();
if (c == STOP) return END();
if (c != 'R') return 1;
// R found
printf ("RFMKCR found\n");
return 1;
}
int END(void)
{
return 0;
}
int main()
{
printf ("\n*start*\n");
while(START());
printf ("*the end*\n");
return 0;
}
溶液2）
#include <stdio.h>
#include <stdlib.h>
#define STOP '!'
int START()
{
int c;
START:
c = getchar1();
if (c == 'A') goto AWY;
if (c == 'R') goto RFMKCR;
if (c == STOP) goto END;
goto START;
AWY: // A found
c = getchar1();
if (c == 'A') goto AWY;
if (c == 'R') goto RFMKCR;
if (c == STOP) goto END;
if (c != 'W') goto START;
// W found
c = getchar1();
if (c == 'A') goto AWY;
if (c == 'R') goto RFMKCR;
if (c == STOP) goto END;
if (c != 'Y') goto START;
// Y found
printf ("AWY found\n");
goto START;
RFMKCR: // R found
c = getchar1();
if (c == 'A') goto AWY;
if (c == 'R') goto RFMKCR;
if (c == STOP) goto END;
if (c != 'F') goto START;
// F found
c = getchar1();
if (c == 'A') goto AWY;
if (c == 'R') goto RFMKCR;
if (c == '!') goto END;
if (c != 'M') goto START;
// M found
c = getchar1();
if (c == 'A') goto AWY;
if (c == 'R') goto RFMKCR;
if (c == '!') goto END;
if (c != 'K') goto START;
// K found
c = getchar1();
if (c == 'A') goto AWY;
if (c == 'R') goto RFMKCR;
if (c == STOP) goto END;
if (c != 'C') goto START;
// C found
c = getchar1();
if (c == 'A') goto AWY;
if (c == STOP) goto END;
if (c != 'R') goto START;
// R found
printf ("RFMKCR found\n");
goto START;
END:
return 0;
}
int getchar1(void) // wraper around your input
{
char in;
in = getchar(); // or scanf ("%c", &in);
return in;
}
int main()
{
printf ("*start*\n");
START();
printf ("*the end*\n");
return 0;
}
同じ出力は、両方のソリューションによって生成されます。
INPUTのためのOUTPUT：AAWY AAWWAWY RRRFMKCR A A WY AWRFMCR AAA!
*start*
AWY found
AWY found
RFMKCR found
*the end*
3）ソリューション
/******************************************************************************
CLASSICAL STATE MACHINE APPROACH
- take a notice how the generic `next` function service transitions
- together with the `start` helper.
- `next` and `start` have the same functions signatures
- and can be replaced with a function pointers
The resulting code is more complicated than previous two examples.
However:
a) the input is taken only from one place (inside the while loop)
b) the generic nature of the code allows easy customization/
*******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#define STOP '!' // character chosen to stop processing
#define END 0
#define IDLE 1
#define START 2
#define AWY_A 3
#define AWY_W 4
#define AWY_Y 5
#define RFMKCR_R 6
#define RFMKCR_F 7
#define RFMKCR_M 8
#define RFMKCR_K 9
#define RFMKCR_C 10
#define RFMKCR_R_END 11
#define AWY_FOUND 12
#define RFMKCR_FOUND 13
#define TO_BE_CALCULATED 14
#define UNKNOWN_STATE 15
// we keep here the current state and next state to which we will transit
struct state_machine_state
{
int current_state;
int next_state;
unsigned int debug_flag;
};
int getchar1 (void);
int start(struct state_machine_state *p, int c, int current_state, int char_expected, int next_state);
int next(struct state_machine_state *p, int c, int current_state, int char_expected, int next_state);
int state_machine(struct state_machine_state *p, int c);
int processing(void);
int getchar1 (void)
{
int in;
in = getchar(); //char in = scanf ("%c", &in);
return in;
}
int next(struct state_machine_state *p, int c, int current_state, int char_expected, int next_state)
{
// This generic function provides transitions to the required states based on the input `c` character
// If c matches the expected character than we transition to known apriori next state
// If the input `c` does not match expected character then we re-start the hunt for patterns
if (c == char_expected)
{
if(p->debug_flag)
printf("++: c=%c cs=%d next=%d \n", c, p->next_state, next_state);
p->current_state = current_state;
p->next_state = next_state;
return next_state;
}
return (start(p, c, current_state, c, TO_BE_CALCULATED));
}
int start(struct state_machine_state *p, int c, int current_state, int char_expected, int next_state)
{
// We hunt for the following
// - start of the AWY pattern: 'A'
// - start of the RFMKCR pattern 'R'
// - special termination character (see: #define STOP )
// If none of the above is found than continue the hunt, we stay in the START state
switch(c)
{
case 'A': return(next(p, c, AWY_A, 'A', AWY_W)); // == p->current_state = AWY_A; p->next_state = AWY_W; return AWY_W;
case 'R': return(next(p, c, RFMKCR_R, 'R', RFMKCR_F)); // == p->current_state = RFMKCR_R; p->next_state = RFMKCR_F; return RFMKCR_F;
case STOP: return(next(p, c, END, STOP, END)); // == p->current_state = END; p->next_state = END; return END;
default: return(next(p, c, START, c, START)); // == p->current_state = START; p->next_state = START; return START;
}
}
int state_machine(struct state_machine_state *p, int c)
{
// state machine gets two inputs, pointer `p` to state_machine_state structure
// and current char `c` to be processed
switch (p->next_state)
{
// search for the beginning of the pattern:
case START: return(start(p, c, START, c, TO_BE_CALCULATED)); // can return: AWY_W, RFMKCR_F, START, END
// process all expected transitions for the AWY pattern
// A->W->Y
case AWY_W: return(next(p, c, AWY_W, 'W', AWY_Y)); // can return AWY_W
case AWY_Y: return(next(p, c, AWY_Y, 'Y', AWY_FOUND)); // can return AWY_FOUND
// process proper transitions for the RFMKCR pattern:
// R->F->M->K->C->R
case RFMKCR_F: return (next(p, c, RFMKCR_F, 'F', RFMKCR_M));
case RFMKCR_M: return (next(p, c, RFMKCR_M, 'M', RFMKCR_K));
case RFMKCR_K: return (next(p, c, RFMKCR_K, 'K', RFMKCR_C));
case RFMKCR_C: return (next(p, c, RFMKCR_C, 'C', RFMKCR_R_END));
case RFMKCR_R_END: return (next(p, c, RFMKCR_R_END, 'R', RFMKCR_FOUND)); // can retun RFMKCR_FOUND
default: printf ("UNKNOWN STATE! %d=\n", p->next_state); return(start(p,c,UNKNOWN_STATE,c,TO_BE_CALCULATED)); // We should never come here!!!
}
}
int processing(void)
{
int c;
int next_state;
struct state_machine_state s;
// Init state machine:
s.current_state = IDLE;
s.next_state = START;
s.debug_flag = 0; // change to 1 if you need to see transitions
// --
while(1)
{
c = getchar1(); // may state machine designs like to have an input in one place
next_state = state_machine(&s,c); // our main state processor
// We service here special states:
switch(next_state) // s.next_state can be used as well
{
case AWY_FOUND:
printf("AWY found\n"); // we will continue search
next(&s, c, AWY_FOUND, 'Y', START);
break;
case RFMKCR_FOUND: // we will continue search
printf("RFMKCR found\n");
next(&s, c, RFMKCR_FOUND, 'R', START);
break;
case END:
next(&s, c, END, STOP, END);
return 0; // This state terminates processing
default:
// We are not interested in these states!
break;
}
}
return 0;
}
int main()
{
printf ("*start*\n");
processing();
printf ("*the end*\n");
return 0;
}
OUTPUT：
*start*
AAWY A W Y RFMKCRR AWYY!
AWY found
RFMKCR found
AWY found
*the end*
関連する問題
- 1. 文字列パターン検索アルゴリズムスタックオーバーフロー
- 2. 配列内の文字列を文字列で検索する
- 3. Java - 文字列配列の文字列を検索する
- 4. 文字列の配列から文字列を検索する
- 5. 文字列配列でアンドロイドで検索
- 6. 配列に含まれる文字列の検索文字列
- 7. 分割文字列検索パターンObjective-C
- 8. 文字列の配列内の文字列を検索
- 9. 文字列配列名の検索
- 10. リニア検索の配列と文字列
- 11. カサンドラは文字列検索パターンを実装しています
- 12. Excel VBAで文字列内の文字列の配列を検索する
- 13. 反復バイナリ検索 - 文字列配列
- 14. リニア検索配列文字列
- 15. grepl：パターンが含まれていない文字列内での検索
- 16. XPathで文字列のシーケンス内の文字列を検索しようとしています
- 17. 文字列配列アイテム要素内の文字列を検索する
- 18. Magentoの長い検索クエリが空の文字列のホームページ
- 19. テキスト内の文字列のパターンを検索する
- 20. 他の配列から文字列で配列を検索するC＃
- 21. ワイルドカードと文字列を変数配列で検索する
- 22. セル配列から文字列を検索し、新しいセル配列
- 23. 文字列の文字列の検索
- 24. 文字列内のパターンを検索する
- 25. numpy配列のパターンを検索
- 26. 文字列のdjango検索文字列
- 27. Ruby grep - 文字列の一部の配列を検索する
- 28. Javascriptの部分文字列の配列を検索する
- 29. 文字列内の部分文字列の配列を検索します。
- 30. 特定の文字列の文字列配列を検索します。
おそらく、あなたは、ステート・マシンを作ることになっています。 – user3386109
構造体を使用します。リンクされたリストを作成します。検索方法を実装します。私たちにあなたの仕事を教えてください。私たちはあなたの宿題をするためにここにいません。 –