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

【文字列処理アルゴリズム】文字列包含アルゴリズムの設計と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. プログラムコード

  1. /******************************************************************************************
  2.  * 著作権 (C) 2016、Zhou Zhaoxiong。
  3.  *
  4.  * ファイル名: StringContains.c
  5.  * ファイルID: なし
  6. * 概要: 文字列が別の文字列の部分文字列であるかどうかをテストします
  7. * その他の注意: たとえば、「ABC」は「ABCD」の部分文字列です
  8. * 現在のバージョン: V1.0
  9.  * 著者: 周昭雄
  10. * 完成日: 20160216
  11.  *
  12.  ******************************************************************************/
  13.  #include < stdio.h >  
  14.  #include < stdlib.h >   
  15.  
  16.  // データ型を再定義する
  17. typedef signed char INT8;
  18.  typedef 符号なし短整数 UINT16;
  19. 型定義 int INT32;
  20.  typedef 符号なし int UINT32; 
  21.  
  22.  //文字列内の文字とフォーマットを格納する構造体
  23. typedef構造体
  24. {
  25.     INT8 szStrCharArray[101][2]; // 文字列内の異なる文字を格納するための配列。最大100文字がサポートされます
  26.     INT32 iStrCharCount; // 文字列内の異なる文字の数
  27. } StrInfo_T; 
  28.  
  29.  StrInfo_T gtLongerStrInfo = {0};
  30.  StrInfo_T gtShorterStrInfo = {0}; 
  31.  
  32.  
  33.  // 関数宣言
  34. void GetStrChar(INT8 *pszInputStr、INT32 iProcessFlag);
  35.  INT32 判定対象が String の場合(); 
  36.  
  37.  
  38.  /******************************************************************************************
  39.  * 機能説明: 主な機能
  40. * 入力パラメータ: なし
  41. * 出力パラメータ: なし
  42. * 戻り値: 0 - 実行成功 その他 - 実行失敗
  43. * その他の指示: なし
  44. * 変更日 バージョン番号 修正者 変更内容
  45. * -----------------------------------------------------------------
  46.  * 20160216 V1.0 作成者: Zhou Zhaoxiong
  47.  ******************************************************************************/
  48.  INT32 メイン()
  49.  {
  50.     INT8 szLongerStr[500] = {0};
  51.     INT8 szShorterStr[100] = {0}; 
  52.      
  53.     UINT32 iContainFlag = 1 ; // フラグを含む、1-含む、0-含まない
  54.      
  55.     printf("より長い文字列を入力してください: \n");
  56.     scanf("%s", szLongerStr);
  57.     printf(" LongerStr =%s\n", szLongerStr); 
  58.  
  59.     printf("より短い文字列を入力してください: \n");
  60.     scanf("%s", szShorterStr);
  61.     printf(" ShorterStr =%s\n", szShorterStr); 
  62.  
  63.     // ShorterStrの長さがLongerStrより大きい場合は直接返す
  64.     （strlen(szShorterStr) > strlen(szLongerStr)）の場合
  65.     {
  66.         printf("%s は %s より長いです。確認してください!\n", szShorterStr, szLongerStr);
  67.         -1 を返します。
  68.     } 
  69.      
  70.     // 長い文字列内の異なる文字を取得します
  71.     GetStrChar(szLongerStr, 1); 
  72.  
  73.     // 短い文字列内の異なる文字を取得します
  74.     GetStrChar(szShorterStr, 2); 
  75.  
  76.  iContainFlag = JudgeIfContainsStr ();
  77.     iContainFlag == 0 の場合
  78.     {
  79.         printf("%s には %s が含まれていません!\n", szLongerStr, szShorterStr);
  80.     }
  81.     それ以外
  82.     {
  83.         printf("%s には %s が含まれています!\n", szLongerStr, szShorterStr);
  84.     } 
  85.      
  86.     0を返します。
  87.  } 
  88.  
  89.  
  90.  /******************************************************************************************
  91.  * 関数の説明: 文字列内の一意の文字とその数を取得します
  92. * 入力パラメータ: pszInputStr-入力文字列
  93.              iProcessFlag - 処理フラグ (1: 長い文字列を処理、2: 短い文字列を処理)
  94.  * 出力パラメータ: なし
  95. * 戻り値: なし
  96. * その他の指示: なし
  97. * 変更日 バージョン番号 修正者 変更内容
  98. * -----------------------------------------------------------------
  99.  * 20160216 V1.0 作成者: Zhou Zhaoxiong
  100.  ******************************************************************************/
  101.  void GetStrChar(INT8 *pszInputStr、INT32 iProcessFlag)
  102.  {
  103.     INT32 iCharCount = 0 ; // 文字数
  104.     INT8 szInputStr[501] = {0};
  105.     INT8 szCharBuf[2] = {0}; // 単一文字を格納するバッファ
  106.     INT32 iRepeatFlag = 0 ;
  107.     UINT32 iStrPosFlag = 0 ;
  108.     UINT32 iループフラグ= 0 ;
  109.     UINT32 iInputStrLen = 0 ; 
  110.  
  111.     pszInputStr == NULL の場合
  112.     {
  113.         戻る;
  114.     } 
  115.  
  116.  iInputStrLen = strlen (pszInputStr);
  117.     if (iInputStrLen > = 500) // *** 100文字をサポートします
  118.     {
  119.         戻る;
  120.     } 
  121.  
  122.     memcpy(szInputStr、pszInputStr、iInputStrLen); 
  123.  
  124.  iCharCount = 0 ; 
  125.  
  126.     ( iStrPosFlag = 0 ; iStrPosFlag <   iInputStrLen ; iStrPosFlag++) は、
  127.     {
  128. 繰り返しフラグ= 0 ; 
  129.          
  130.         // 取得する文字が既に存在するかどうかを判定する
  131.         memset(szCharBuf, 0x00, sizeof(szCharBuf));
  132.         memcpy(szCharBuf、szInputStr+iStrPosFlag、1); 
  133.  
  134.         // 以前に追加された文字と重複している場合は無視されます
  135.         ( iLoopF​​lag = 0 ; iLoopF​​lag <   iCharCount ; iLoopF​​lag ++)
  136.         {
  137.             if ( iProcessFlag == 1) // 長い文字列を処理する
  138.             {
  139.                 0 == strncmp(gtLongerStrInfo.szStrCharArray[iLoopF​​lag], szCharBuf, 1) の場合)
  140.                 {
  141.  iRepeatFlag = 1 ; // 重複がある場合は無視します
  142.                     壊す;
  143.                 }
  144.             }
  145.             else // 短い文字列を処理する
  146.             {
  147.                 0 == strncmp(gtShorterStrInfo.szStrCharArray[iLoopF​​lag], szCharBuf, 1) の場合)
  148.                 {
  149.  iRepeatFlag = 1 ; // 重複がある場合は無視します
  150.                     壊す;
  151.                 }
  152.             }
  153.         } 
  154.  
  155.         if ( 1 == iRepeatFlag)
  156.         {
  157.             続く;
  158.         } 
  159.  
  160.         if ( iProcessFlag == 1) // 長い文字列を処理する
  161.         {
  162.             strncpy(gtLongerStrInfo.szStrCharArray[iCharCount], szCharBuf, 1);
  163.         }
  164.         else // 短い文字列を処理する
  165.         {
  166.             strncpy(gtShorterStrInfo.szStrCharArray[iCharCount], szCharBuf, 1);
  167.         } 
  168.  
  169.  iCharCount iCharCount = iCharCount + 1;
  170.     } 
  171.  
  172.     if ( iProcessFlag == 1) // 長い文字列を処理する
  173.     {
  174.  gtLongerStrInfo.iStrCharCount = iCharCount ;
  175.     }
  176.     else // 短い文字列を処理する
  177.     {
  178.  gtShorterStrInfo.iStrCharCount = iCharCount ;
  179.     } 
  180.  
  181.     戻る;
  182.  } 
  183.  
  184.  
  185.  /******************************************************************************************
  186.  * 関数の説明: 長い文字列に短い文字列が含まれているかどうかを判定する
  187. * 入力パラメータ: なし
  188. * 出力パラメータ: なし
  189. * 戻り値: 1-含まれる 0-含まれない
  190. * その他の指示: なし
  191. * 変更日 バージョン番号 修正者 変更内容
  192. * -----------------------------------------------------------------
  193.  * 20160216 V1.0 作成者: Zhou Zhaoxiong
  194.  ******************************************************************************/
  195.  INT32 判定対象文字列()
  196.  {
  197.     UINT32 iLongerLoopF​​lag = 0 ;
  198.     UINT32 iShorterLoopF​​lag = 0 ;
  199.     UINT32 iCharIdenticalFlag = 0 ; 
  200.  
  201.     // 短い文字列のすべての文字が長い文字列の文字に含まれているかどうかを判定します
  202.     ( iShorterLoopF​​lag = 0 ; iShorterLoopF​​lag <   gtShorterStrInfo.iStrCharCount ; iShorterLoopF​​lag++)
  203.     {
  204.  iCharIdenticalFlag = 0 ;
  205.         ( iLongerLoopF​​lag = 0 ; iLongerLoopF​​lag <   gtLongerStrInfo.iStrCharCount ; iLongerLoopF​​lag++)
  206.         {
  207.             (strcmp(gtShorterStrInfo.szStrCharArray[iShorterLoopF​​lag], gtLongerStrInfo.szStrCharArray[iLongerLoopF​​lag]) == 0)の場合
  208.             {
  209.  iCharIdenticalFlag = 1 ; // 文字は同じです
  210.                 壊す;
  211.             }
  212.         } 
  213.  
  214.         if ( iCharIdenticalFlag == 0) // 2つの文字列に異なる文字があることを示します
  215.         {
  216.             0を返します。
  217.         }
  218.     } 
  219.  
  220.     1 を返します。
  221.  }

5. プログラムのテスト

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

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

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

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

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

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

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

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

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

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

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

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

6. 需要拡大

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

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

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

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

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

<<:  [文字列処理アルゴリズム] 入力文字列の各単語の順序を逆にするアルゴリズム設計とCコード実装

>>:  ビッグデータの3つの柱：データ、ブロックチェーン、アルゴリズム

推薦する

...

人工知能の旅：プロトタイピングは始まりに過ぎない

国内外で人工知能や機械学習のチームが大きな成果のニュースを共有し続けているのをよく見かけますが、実用...

Dianping.com における検索関連性技術の探求と実践

著者: Xiaoya、Shen Yuan、Judy など1. 背景レビュー検索は、Dianping ...

マイクロソフト、中小企業向けにCopilot AIアシスタントを導入、個人向けにプレミアムサービスを開始

マイクロソフトは火曜日、中小企業が同社の生産性向上アプリ内で仮想アシスタント「Copilot」を利用...

フォーブス誌の2020年AIに関するトップ10予測: 人工知能はますます「疎外」されつつある

人工知能 (AI) は間違いなく 2010 年代のテクノロジーのテーマであり、新しい 10 年が始ま...

OpenAIがChatGPTの「カスタム指示」機能を全ユーザーに公開

米国現地時間8月11日木曜日、人工知能研究企業OpenAIは、ChatGPTの「カスタム指示」機能を...

これらの5種類の情報はAIチャットボットに決して開示されるべきではない

翻訳者 | ブガッティレビュー | Chonglou AIチャットボットの人気が急上昇しています。チ...

...

...

Pythonで検索アルゴリズムを実装する方法を教えます

[[439902]]この記事では、次の検索アルゴリズムについて説明します。線形探索バイナリ検索補間検...

人工知能を活用した新しい小売無人店舗の発展展望は？

[[253800]] 2017年にジャック・マーがニューリテールの概念を提唱して以来、雨後の筍のよ...

突風か潮か？AIが音声だけで止まってしまったら、一体いつまで苦労し続けることができるのだろうか？

いつからか、「人工知能」という言葉はテクノロジー界で徐々に広まり、今では現在のテクノロジー製品や業界...

...

人工知能がITを変える5つの方法

IT サービス デスクからデータ分析の最前線、新しいツール、戦略、関係まで、AI は IT 組織をど...

人工知能には自由意志があるのでしょうか?

[[388433]]伝統的な哲学的観点では、「自由意志」は人間だけが持つ特別な能力であり、この能力...