【文字列処理アルゴリズム】文字列包含アルゴリズムの設計とCコード実装

1. 要件の説明

長い文字列と短い文字列が与えられた場合、短い文字列のすべての文字が長い文字列に含まれているかどうかを判断するプログラムを作成します。はいの場合、長い文字列に短い文字列が含まれます。それ以外の場合は含まれません。

できるだけ多くのケースをカバーするために、文字列には大文字と小文字の英語の文字、数字、およびさまざまな句読点を含めることができ、大文字と小文字が区別されます。

以下にいくつかの例を挙げて説明します。

1. 長い文字列が「ABCDE」で、短い文字列が「ADC」の場合、短い文字列のすべての文字が長い文字列に含まれます。つまり、長い文字列には短い文字列が含まれます。

2. 長い文字列が「ABCDE」で、短い文字列が「ADCF」の場合、短い文字列のすべての文字が長い文字列に含まれるわけではありません。つまり、長い文字列には短い文字列が含まれません。

3. 長い文字列が「ABCDE」で、短い文字列が「AAB」の場合、短い文字列のすべての文字が長い文字列に含まれます。つまり、長い文字列には短い文字列が含まれます。

[[180306]]

2. アルゴリズム設計

人間の体が個々の細胞で構成されているのと同じように、文字列も個々の文字で構成されていることは誰もが知っています。ある文字列のすべての文字が別の文字列に存在する場合、その文字列は別の文字列に含まれています。

したがって、まず 2 つの文字列のすべての文字を見つけて、次に短い文字列のすべての文字が長い文字列に現れるかどうかを判断することを検討できます。そうであれば、2 つの文字列は包含と包含される関係にあります。そうでない場合、2 つの文字列は「他人」です。

プログラムの全体的な流れを図 1 に示します。

図1 プログラムの全体的なプロセス

3. 特別なプロセスに関する考慮事項

プログラムを作成する過程では、次のような 2 つの入力文字列の長さと形式を考慮する必要があります。

1. 入力エラーにより短い文字列の長さが長い文字列より長くなった場合、プログラムはそれ以上の処理を行わずにそのまま戻ります。

2. 入力文字列の途中にスペースを入れることはできません。スペースが入った場合は、スペースの前の内容のみが入力文字列として使用できます。

3. 入力文字列には、文字（大文字と小文字が区別されます）、数字、句読点、その他の文字を含めることができます。

4. プログラム処理を容易にするために、長い文字列の最大長を 500 バイトに設定し、短い文字列の最大長を 100 バイトに設定します。

4. プログラムコード

/******************************************************************************************
 * 著作権 (C) 2016、Zhou Zhaoxiong。
 *
 * ファイル名: StringContains.c
 * ファイルID: なし
* 概要: 文字列が別の文字列の部分文字列であるかどうかをテストします
* その他の注意: たとえば、「ABC」は「ABCD」の部分文字列です
* 現在のバージョン: V1.0
 * 著者: 周昭雄
* 完成日: 20160216
 *
 ******************************************************************************/
 #include < stdio.h >  
 #include < stdlib.h >   
 
 // データ型を再定義する
typedef signed char INT8;
 typedef 符号なし短整数 UINT16;
型定義 int INT32;
 typedef 符号なし int UINT32; 
 
 //文字列内の文字とフォーマットを格納する構造体
typedef構造体
{
    INT8 szStrCharArray[101][2]; // 文字列内の異なる文字を格納するための配列。最大100文字がサポートされます
    INT32 iStrCharCount; // 文字列内の異なる文字の数
} StrInfo_T; 
 
 StrInfo_T gtLongerStrInfo = {0};
 StrInfo_T gtShorterStrInfo = {0}; 
 
 
 // 関数宣言
void GetStrChar(INT8 *pszInputStr、INT32 iProcessFlag);
 INT32 判定対象が String の場合(); 
 
 
 /******************************************************************************************
 * 機能説明: 主な機能
* 入力パラメータ: なし
* 出力パラメータ: なし
* 戻り値: 0 - 実行成功 その他 - 実行失敗
* その他の指示: なし
* 変更日 バージョン番号 修正者 変更内容
* -----------------------------------------------------------------
 * 20160216 V1.0 作成者: Zhou Zhaoxiong
 ******************************************************************************/
 INT32 メイン()
 {
    INT8 szLongerStr[500] = {0};
    INT8 szShorterStr[100] = {0}; 
     
    UINT32 iContainFlag = 1 ; // フラグを含む、1-含む、0-含まない
     
    printf("より長い文字列を入力してください: \n");
    scanf("%s", szLongerStr);
    printf(" LongerStr =%s\n", szLongerStr); 
 
    printf("より短い文字列を入力してください: \n");
    scanf("%s", szShorterStr);
    printf(" ShorterStr =%s\n", szShorterStr); 
 
    // ShorterStrの長さがLongerStrより大きい場合は直接返す
    （strlen(szShorterStr) > strlen(szLongerStr)）の場合
    {
        printf("%s は %s より長いです。確認してください!\n", szShorterStr, szLongerStr);
        -1 を返します。
    } 
     
    // 長い文字列内の異なる文字を取得します
    GetStrChar(szLongerStr, 1); 
 
    // 短い文字列内の異なる文字を取得します
    GetStrChar(szShorterStr, 2); 
 
 iContainFlag = JudgeIfContainsStr ();
    iContainFlag == 0 の場合
    {
        printf("%s には %s が含まれていません!\n", szLongerStr, szShorterStr);
    }
    それ以外
    {
        printf("%s には %s が含まれています!\n", szLongerStr, szShorterStr);
    } 
     
    0を返します。
 } 
 
 
 /******************************************************************************************
 * 関数の説明: 文字列内の一意の文字とその数を取得します
* 入力パラメータ: pszInputStr-入力文字列
             iProcessFlag - 処理フラグ (1: 長い文字列を処理、2: 短い文字列を処理)
 * 出力パラメータ: なし
* 戻り値: なし
* その他の指示: なし
* 変更日 バージョン番号 修正者 変更内容
* -----------------------------------------------------------------
 * 20160216 V1.0 作成者: Zhou Zhaoxiong
 ******************************************************************************/
 void GetStrChar(INT8 *pszInputStr、INT32 iProcessFlag)
 {
    INT32 iCharCount = 0 ; // 文字数
    INT8 szInputStr[501] = {0};
    INT8 szCharBuf[2] = {0}; // 単一文字を格納するバッファ
    INT32 iRepeatFlag = 0 ;
    UINT32 iStrPosFlag = 0 ;
    UINT32 iループフラグ= 0 ;
    UINT32 iInputStrLen = 0 ; 
 
    pszInputStr == NULL の場合
    {
        戻る;
    } 
 
 iInputStrLen = strlen (pszInputStr);
    if (iInputStrLen > = 500) // *** 100文字をサポートします
    {
        戻る;
    } 
 
    memcpy(szInputStr、pszInputStr、iInputStrLen); 
 
 iCharCount = 0 ; 
 
    ( iStrPosFlag = 0 ; iStrPosFlag <   iInputStrLen ; iStrPosFlag++) は、
    {
繰り返しフラグ= 0 ; 
         
        // 取得する文字が既に存在するかどうかを判定する
        memset(szCharBuf, 0x00, sizeof(szCharBuf));
        memcpy(szCharBuf、szInputStr+iStrPosFlag、1); 
 
        // 以前に追加された文字と重複している場合は無視されます
        ( iLoopF​​lag = 0 ; iLoopF​​lag <   iCharCount ; iLoopF​​lag ++)
        {
            if ( iProcessFlag == 1) // 長い文字列を処理する
            {
                0 == strncmp(gtLongerStrInfo.szStrCharArray[iLoopF​​lag], szCharBuf, 1) の場合)
                {
 iRepeatFlag = 1 ; // 重複がある場合は無視します
                    壊す;
                }
            }
            else // 短い文字列を処理する
            {
                0 == strncmp(gtShorterStrInfo.szStrCharArray[iLoopF​​lag], szCharBuf, 1) の場合)
                {
 iRepeatFlag = 1 ; // 重複がある場合は無視します
                    壊す;
                }
            }
        } 
 
        if ( 1 == iRepeatFlag)
        {
            続く;
        } 
 
        if ( iProcessFlag == 1) // 長い文字列を処理する
        {
            strncpy(gtLongerStrInfo.szStrCharArray[iCharCount], szCharBuf, 1);
        }
        else // 短い文字列を処理する
        {
            strncpy(gtShorterStrInfo.szStrCharArray[iCharCount], szCharBuf, 1);
        } 
 
 iCharCount iCharCount = iCharCount + 1;
    } 
 
    if ( iProcessFlag == 1) // 長い文字列を処理する
    {
 gtLongerStrInfo.iStrCharCount = iCharCount ;
    }
    else // 短い文字列を処理する
    {
 gtShorterStrInfo.iStrCharCount = iCharCount ;
    } 
 
    戻る;
 } 
 
 
 /******************************************************************************************
 * 関数の説明: 長い文字列に短い文字列が含まれているかどうかを判定する
* 入力パラメータ: なし
* 出力パラメータ: なし
* 戻り値: 1-含まれる 0-含まれない
* その他の指示: なし
* 変更日 バージョン番号 修正者 変更内容
* -----------------------------------------------------------------
 * 20160216 V1.0 作成者: Zhou Zhaoxiong
 ******************************************************************************/
 INT32 判定対象文字列()
 {
    UINT32 iLongerLoopF​​lag = 0 ;
    UINT32 iShorterLoopF​​lag = 0 ;
    UINT32 iCharIdenticalFlag = 0 ; 
 
    // 短い文字列のすべての文字が長い文字列の文字に含まれているかどうかを判定します
    ( iShorterLoopF​​lag = 0 ; iShorterLoopF​​lag <   gtShorterStrInfo.iStrCharCount ; iShorterLoopF​​lag++)
    {
 iCharIdenticalFlag = 0 ;
        ( iLongerLoopF​​lag = 0 ; iLongerLoopF​​lag <   gtLongerStrInfo.iStrCharCount ; iLongerLoopF​​lag++)
        {
            (strcmp(gtShorterStrInfo.szStrCharArray[iShorterLoopF​​lag], gtLongerStrInfo.szStrCharArray[iLongerLoopF​​lag]) == 0)の場合
            {
 iCharIdenticalFlag = 1 ; // 文字は同じです
                壊す;
            }
        } 
 
        if ( iCharIdenticalFlag == 0) // 2つの文字列に異なる文字があることを示します
        {
            0を返します。
        }
    } 
 
    1 を返します。
 }

5. プログラムのテスト

記述したプログラム「StringContains.c」を Linux マシンにアップロードし、「gcc -g -o StringContainsStringContains.c」コマンドを使用してプログラムをコンパイルし、「StringContains」ファイルを生成します。以下はプログラムの詳細なテストです。

1. 長い文字列が「ABCDF」で、短い文字列が「AF」の場合、プログラムは次のように実行されます。

より長い文字列を入力してください:
 ABCDF
長いStr = ABCDF  
より短い文字列を入力してください:
 AF
ショートストル= AF  
 ABCDFにはAFが含まれています！

2. 長い文字列が「AB」で、短い文字列が「ABC」の場合、プログラムは次のように実行されます。

より長い文字列を入力してください:
 AB
ロングストル= AB  
より短い文字列を入力してください:
 ABC
ショートStr = ABC  
 ABC は AB より長いです。確認してください。

3. 長い文字列が「awe」で、短い文字列が「rf」の場合、プログラムは次のように実行されます。

より長い文字列を入力してください:
畏敬の念
LongerStr =畏敬の念 
より短い文字列を入力してください:
無線周波数
ショートStr = rf  
 awe には rf が含まれていません。

4. 長い文字列が「`11245」で、短い文字列が「45」の場合、プログラムは次のように実行されます。

より長い文字列を入力してください:
 `11245
長いStr = `11245
より短い文字列を入力してください:
 45
ショートストレングス= 45  
 「11245 には 45 が含まれています!」

5. 長い文字列が「123」で、短い文字列が「123 45」の場合、プログラムは次のように実行されます。

より長い文字列を入力してください:
 123
ロングストル= 123  
より短い文字列を入力してください:
 123 45
ショートストル= 123  
 123 には 123 が含まれています!

プログラムは、上で検討したいくつかの特殊なケースを正しく処理できることがわかります。

6. 需要拡大

この記事の要件と手順に基づいて、要件の次の拡張を検討できます。

1. 入力文字列を文字のみに制限します。他の文字が含まれている場合は、処理せずに直接終了します。

2. 短い文字列のすべての文字が長い文字列に含まれているが、特定の文字が短い文字列に長い文字列よりも多く出現する場合、長い文字列には短い文字列が含まれていないと見なされます。

[この記事は51CTOコラムニストの周兆雄氏によるオリジナル記事です。著者のWeChat公開アカウント：周の論理（logiczhou）]

この著者の他の記事を読むにはここをクリックしてください