[文字列処理アルゴリズム] 最長共通部分文字列を取得するためのアルゴリズム設計とCコード実装

1. 要件の説明

2 つの文字列を入力し、2 つの文字列の最長共通部分文字列を取得するプログラムを作成します。

たとえば、入力文字列が「abcdef」と「fecdba」の場合、これら 2 つの文字列の最長共通部分文字列は「cd」です。

2. アルゴリズム設計

まず、2 つの文字列で最初の等しい文字を見つけ、次に後方に移動して、対応する位置の文字が等しいかどうかを比較します。

つまり、文字列 1 が「1234abcd」で文字列 2 が「abd」の場合、まず文字列 1 の 5 番目の文字「a」が文字列 2 の最初の文字「a」と等しいことがわかり、次に文字列 1 の 6 番目の文字「b」が文字列 2 の 2 番目の文字「b」と等しく、次に文字列 1 の 7 番目の文字「c」が文字列 2 の 3 番目の文字「d」と等しくないことが判明し、この時点で比較が終了します。つまり、文字列 1 と文字列 2 の最長共通部分文字列は「ab」です。

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

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

1. 2 つの入力文字列の 1 つに中国語の文字が含まれている場合、プログラムは後続の処理を実行せずに直接戻ります。

2. 2 つの入力文字列の 1 つにスペースが含まれている場合、プログラムは後続の操作のためにスペースの前の文字列を取得します。

4. プログラムコード

/******************************************************************************************
 * 著作権 (C) 2016、Zhou Zhaoxiong。
 *
 * ファイル名: GetLCS.c
 * ファイルID: なし
* 概要: 2つの文字列の最長共通部分文字列を見つける
* その他の注意: たとえば、「abcdef」と「bcf」の最長共通部分文字列は「bc」です。
 * 現在のバージョン: V1.0
 * 著者: 周昭雄
* 完成日: 20160322
 *
 ******************************************************************************/
 #include < stdio.h >  
 #include <文字列.h >  
 #include < stdlib.h >   
 
 
 // データ型を再定義する
typedef signed char INT8;
型定義 int INT32;
 typedef 符号なし int UINT32; 
 
 // 関数宣言
void GetLCSOfTwoStr(INT8 *pszInputStr1、INT8 *pszInputStr2); 
 
 
 /******************************************************************************************
 * 機能説明: 主な機能
* 入力パラメータ: なし
* 出力パラメータ: なし
* 戻り値: 0 - 実行成功 その他 - 実行失敗
* その他の指示: なし
* 変更日 バージョン番号 修正者 変更内容
* ---------------------------------------------------------------------
 * 20160322 V1.0 作成者: Zhou Zhaoxiong
 ******************************************************************************/
 INT32 メイン()
 {
    INT8 szInputStr1[100] = {0};
    INT8 szInputStr2[100] = {0};
    UINT32 iPosFlag = 0 ; 
     
    printf("文字列1を入力してください:\n");
    scanf("%s", szInputStr1);
    printf(" InputStr1 =%s\n", szInputStr1); 
 
    printf("文字列2を入力してください:\n");
    scanf("%s", szInputStr2);
    printf(" InputStr2 =%s\n", szInputStr2); 
 
    // まず中国語の文字があるかどうかを確認します
    ( iPosFlag = 0 ; iPosFlag <   strlen (szInputStr1); iPosFlag++)
    {
        if (szInputStr1[iPosFlag] <   0 ) // 0未満は中国語の文字が含まれていることを意味します
        {
            printf("%s には中国語の文字が含まれています。確認してください!\n", szInputStr1);
            -1 を返します。
        }
    } 
 
    ( iPosFlag = 0 ; iPosFlag <   strlen (szInputStr2); iPosFlag++)
    {
        if (szInputStr2[iPosFlag] <   0 ) // 0未満は中国語の文字が含まれていることを意味します
        {
            printf("%s には中国語の文字が含まれています。確認してください!\n", szInputStr2);
            -1 を返します。
        }
    } 
 
    // 関数を再度呼び出して、2つの文字列の最長共通部分文字列を取得します
    GetLCSOfTwoStr(szInputStr1、szInputStr2); 
 
    0を返します。
 } 
 
 
 /******************************************************************************************
 * 関数の説明: 2つの文字列の最長共通部分文字列を取得します
* 入力パラメータ: pszInputStr1-入力文字列1
             pszInputStr2 - 入力文字列2
 * 出力パラメータ: なし
* 戻り値: なし
* その他の指示: なし
* 変更日 バージョン番号 修正者 変更内容
* ---------------------------------------------------------------------
 * 20160322 V1.0 作成者: Zhou Zhaoxiong
 ******************************************************************************/
 void GetLCSOfTwoStr(INT8 *pszInputStr1、INT8 *pszInputStr2)
 {
    UINT32 iInnerLoopF​​lag = 0 ;
    UINT32 iOutterLoopF​​lag = 0 ;
    UINT32 iPosFlag = 0 ;
    UINT32 iLCSLen = 0 ;
    INT32 i開始位置= -1;
    INT8 szLCS[100] = {0}; 
     
    pszInputStr1 == NULL || pszInputStr2 == NULLの場合
    {
        戻る;
    } 
 
    ( iOutterLoopF ​​lag = 0 ; iOutterLoopF​​lag <   strlen (pszInputStr1); iOutterLoopF​​lag++)
    {
        ( iInnerLoopF​​lag = 0 ; iInnerLoopF​​lag <   strlen (pszInputStr2); iInnerLoopF​​lag++)
        {
            pszInputStr1[iOutterLoopF​​lag] == pszInputStr2[iInnerLoopF​​lag]の場合
            {
                ( iPosFlag = 1 ; pszInputStr1[iOutterLoopF​​lag+iPosFlag] != '\0'; iPosFlag ++)の場合
                {
                    if (pszInputStr1[iOutterLoopF​​lag+iPosFlag] != pszInputStr2[iInnerLoopF​​lag+iPosFlag]) // 等しくない文字が見つかった場合は比較を終了します
                    {
                        壊す;
                    }
                } 
 
                if (iLCSLen <   iPosフラグ)
                {
 iLCSLen = iPosFlag ;
 iStartPos = iOutterLoopF​​lag ;
                }
            }
        }
    } 
   
    ( iStartPos == -1 の場合)
    {
        memset(szLCS, 0x00, sizeof(szLCS));
    }
    それ以外
    {
        memcpy(szLCS, &pszInputStr1[iStartPos], iLCSLen);
    } 
 
    (iLCSLen > 0)の場合
    {
        printf("%s と %s の最長共通部分文字列は: %s、その長さは: %d\n", pszInputStr1, pszInputStr2, szLCS, iLCSLen);
    }
    それ以外
    {
        printf("%s と %s には共通の部分文字列がありません!\n", pszInputStr1, pszInputStr2);
    }
 }

5. プログラムのテスト

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

1. 入力文字列 1 が「abcdef」、文字列 2 が「hijkabm」の場合、プログラムは次のように実行されます。

文字列1を入力してください:
 ABCデフ
入力Str1 = abcdef  
文字列2を入力してください:
ヒジカブム
入力Str2 = hijkabm  
 abcdefとhijkabmの最長共通部分文字列はabであり、その長さは2である。

2. 入力文字列 1 が「1234!@#」、文字列 2 が「5678!@#1」の場合、プログラムは次のように実行されます。

文字列1を入力してください:
 1234!@#
入力Str1 = 1234 !@#
文字列2を入力してください:
 5678!@#1
入力Str2 = 5678 !@#1
 1234!@#と5678!@#1の最長共通部分文字列は:!@#で、その長さは: 3

3. 入力文字列 1 が「123你好」、文字列 2 が「123」の場合、プログラムは次のように実行されます。

文字列1を入力してください:
 123 こんにちは
InputStr1 = 123こんにちは
文字列2を入力してください:
 123
入力Str2 = 123  
 123Helloには中国語の文字がありますので、確認してください。

4. 入力文字列 1 が「123abc」、文字列 2 が「abd ef」の場合、プログラムは次のように実行されます。

文字列1を入力してください:
 123abc
入力Str1 = 123abc  
文字列2を入力してください:
アブドエフ
入力Str2 = abd  
 123abcとabdの最長共通部分文字列はabであり、その長さは2である。

5. 入力文字列 1 が「abcdef」、文字列 2 が「123456」の場合、プログラムは次のように実行されます。

文字列1を入力してください:
 ABCデフ
入力Str1 = abcdef  
文字列2を入力してください:
 123456
入力Str2 = 123456  
 abcdef と 123456 には共通の部分文字列がありません。

6. 需要拡大

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

1. 2 つの文字列に複数の最長共通部分文字列がある場合、それらを出力する必要があります。つまり、文字列 1 が「1234abcd」で文字列 2 が「abd12」の場合、プログラムによって入力される最長共通部分文字列は「12」と「ab」です。

2. 入力文字列に中国語の文字が出現できないという制限はありません。つまり、文字列 1 が「我们123」で文字列 2 が「我们」の場合、最長共通部分文字列は「我们」です。

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

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