【字符串處理算法】字符串包含的算法設計及C代碼實現

作者：周兆熊 2016-12-30 13:32:24

開發開發工具算法

今天講一講字符串包含的算法設計及C代碼實現。

一、需求描述

給定一個長字符串和一個短字符串，編寫程序判斷短字符串中的所有字符是否都在長字符串中。如果是，則長字符串包含短字符串;反之，不包含。

為了盡量包含大多數情況，字符串中可以包含大小寫英文字母、數字和各種標點符號，并且區分大小寫字母。

下面舉幾個例子予以說明：

1.如果長字符串是“ABCDE”，短字符串是“ADC”，那么短字符串中的所有字符都在長字符串中，即長字符串包含了短字符串。

2.如果長字符串是“ABCDE”，短字符串是“ADCF”，那么短字符串中不是所有字符都在長字符串中，即長字符串不包含了短字符串。

3.如果長字符串是“ABCDE”，短字符串是“AAB”，那么短字符串中的所有字符都在長字符串中，即長字符串包含了短字符串。

[[180306]]

二、算法設計

我們都知道，就像人體是由一個個的細胞組成一樣，一個字符串是由一個個的字符組成。如果組成某個字符串的所有字符都在另一個字符串中，那么這個字符串就被另一個字符串包含。

因此，我們可以考慮先將兩個字符串中的所有字符都找出來，再判斷較短的字符串中的所有字符是否都出現在了較長的字符串中。如果是，那么兩個字符串是包含與被包含的關系;如果不是，那么兩個字符串則“形同陌路”。

程序的總體流程如圖1所示。

圖1 程序的總體流程

三、特殊流程考慮

在編寫程序的過程中，我們要對輸入的兩個字符串的長度及格式多做考慮，如：

1.如果輸入失誤，導致短字符串的長度大于了長字符串，那么程序直接返回，不進行后續處理。

2.不允許在輸入字符串的中間出現空格，如果出現了，只能把空格前面的內容作為輸入的字符串。

3.輸入字符串可以包含字母(區分大小寫)、數字、標點符號等字符。

4.為了方便程序處理，設定較長的字符串最長為500個字節，較短的字符串最長為100個字節。

四、程序代碼

/********************************************************************** 
* 版權所有 (C)2016, Zhou Zhaoxiong。 
* 
* 文件名稱： StringContains.c 
* 文件標識： 無 
* 內容摘要： 測試一個字符串是否是另一個字符串的子串 
* 其它說明： 例如, "ABC"是"ABCD"的子串 
* 當前版本： V1.0 
* 作    者： Zhou Zhaoxiong 
* 完成日期： 20160216 
* 
**********************************************************************/ 
#include <stdio.h> 
#include <stdlib.h> 
 
// 重新定義數據類型 
typedef signed   char       INT8; 
typedef unsigned short int  UINT16; 
typedef          int        INT32; 
typedef unsigned int        UINT32; 
 
// 存放字符串中的字符和格式的結構體 
typedef struct 
{ 
    INT8   szStrCharArray[101][2];     // 字符串中不相同的字符的存放數組，***支持100個 
    INT32  iStrCharCount;              // 字符串中不相同的字符的個數 
} StrInfo_T; 
 
StrInfo_T gtLongerStrInfo  = {0}; 
StrInfo_T gtShorterStrInfo = {0}; 
 
 
// 函數聲明 
void GetStrChar(INT8 *pszInputStr, INT32 iProcessFlag); 
INT32 JudgeIfContainsStr(); 
 
 
/********************************************************************** 
* 功能描述： 主函數 
* 輸入參數： 無 
* 輸出參數： 無 
* 返 回 值： 0-執行成功   其它-執行失敗 
* 其它說明： 無 
* 修改日期        版本號       修改人          修改內容 
* ----------------------------------------------------------------- 
* 20160216        V1.0     Zhou Zhaoxiong        創建 
***********************************************************************/ 
INT32 main() 
{ 
    INT8   szLongerStr[500]   = {0}; 
    INT8   szShorterStr[100]  = {0}; 
     
    UINT32 iContainFlag = 1;     // 包含標志, 1-包含, 0-不包含 
     
    printf("Please input the longer string: \n"); 
    scanf("%s", szLongerStr); 
    printf("LongerStr=%s\n", szLongerStr); 
 
    printf("Please input the shorter string: \n"); 
    scanf("%s", szShorterStr); 
    printf("ShorterStr=%s\n", szShorterStr); 
 
    // 如果ShorterStr的長度大于LongerStr, 則直接返回 
    if (strlen(szShorterStr) > strlen(szLongerStr)) 
    { 
        printf("%s is longer than %s, please check!\n", szShorterStr, szLongerStr); 
        return -1; 
    } 
     
    // 獲取較長的字符串中的不同的字符 
    GetStrChar(szLongerStr, 1); 
 
    // 獲取較短的字符串中的不同的字符 
    GetStrChar(szShorterStr, 2); 
 
    iContainFlag = JudgeIfContainsStr(); 
    if (iContainFlag == 0) 
    { 
        printf("%s doesn't contain %s!\n", szLongerStr, szShorterStr); 
    } 
    else 
    { 
        printf("%s contains %s!\n", szLongerStr, szShorterStr); 
    } 
     
    return 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 iLoopFlag       = 0; 
    UINT32 iInputStrLen    = 0; 
 
    if (pszInputStr == NULL) 
    { 
        return; 
    } 
 
    iInputStrLen = strlen(pszInputStr); 
    if (iInputStrLen >= 500)  // ***支持100個字母 
    { 
        return; 
    } 
 
    memcpy(szInputStr, pszInputStr, iInputStrLen); 
 
    iCharCount = 0; 
 
    for (iStrPosFlag = 0; iStrPosFlag < iInputStrLen; iStrPosFlag ++) 
    { 
        iRepeatFlag = 0; 
         
        // 判斷正要獲取的字符是否已經存在了 
        memset(szCharBuf, 0x00, sizeof(szCharBuf)); 
        memcpy(szCharBuf, szInputStr+iStrPosFlag, 1); 
 
        // 若與之前已經加入的字符重復, 則忽略 
        for (iLoopFlag = 0; iLoopFlag < iCharCount; iLoopFlag ++) 
        { 
            if (iProcessFlag == 1)    // 處理長字符串 
            { 
                if (0 == strncmp(gtLongerStrInfo.szStrCharArray[iLoopFlag], szCharBuf, 1)) 
                { 
                    iRepeatFlag = 1;  // 有重復的, 直接忽略 
                    break; 
                } 
            } 
            else                     // 處理短字符串 
            { 
                if (0 == strncmp(gtShorterStrInfo.szStrCharArray[iLoopFlag], szCharBuf, 1)) 
                { 
                    iRepeatFlag = 1;  // 有重復的, 直接忽略 
                    break; 
                } 
            } 
        } 
 
        if (1 == iRepeatFlag) 
        { 
            continue; 
        } 
 
        if (iProcessFlag == 1)    // 處理長字符串 
        { 
            strncpy(gtLongerStrInfo.szStrCharArray[iCharCount], szCharBuf, 1); 
        } 
        else                      // 處理短字符串 
        { 
            strncpy(gtShorterStrInfo.szStrCharArray[iCharCount], szCharBuf, 1); 
        } 
 
        iCharCountiCharCount = iCharCount + 1; 
    } 
 
    if (iProcessFlag == 1)    // 處理長字符串 
    { 
        gtLongerStrInfo.iStrCharCount = iCharCount; 
    } 
    else                      // 處理短字符串 
    { 
        gtShorterStrInfo.iStrCharCount = iCharCount; 
    } 
 
    return; 
} 
 
 
/********************************************************************** 
* 功能描述： 判斷長字符串是否包含了短字符串 
* 輸入參數： 無 
* 輸出參數： 無 
* 返 回 值： 1-包含了 0-沒有包含 
* 其它說明： 無 
* 修改日期          版本號         修改人           修改內容 
* --------------------------------------------------------------- 
* 20160216          V1.0       Zhou Zhaoxiong        創建 
***********************************************************************/ 
INT32 JudgeIfContainsStr() 
{ 
    UINT32 iLongerLoopFlag    = 0; 
    UINT32 iShorterLoopFlag   = 0; 
    UINT32 iCharIdenticalFlag = 0; 
 
    // 判斷較短的字符串中的字符是否全部都在較長的字符串中的字符中 
    for (iShorterLoopFlag = 0; iShorterLoopFlag < gtShorterStrInfo.iStrCharCount; iShorterLoopFlag ++) 
    { 
        iCharIdenticalFlag = 0; 
        for (iLongerLoopFlag = 0; iLongerLoopFlag < gtLongerStrInfo.iStrCharCount; iLongerLoopFlag ++) 
        { 
            if (strcmp(gtShorterStrInfo.szStrCharArray[iShorterLoopFlag], gtLongerStrInfo.szStrCharArray[iLongerLoopFlag]) == 0) 
            { 
                iCharIdenticalFlag = 1;    // 字符相同 
                break; 
            } 
        } 
 
        if (iCharIdenticalFlag == 0)     // 表示兩個字符串中有不相同的字符 
        { 
            return 0; 
        } 
    } 
 
    return 1; 
}

五、程序測試

我們將編寫好的程序“StringContains.c”上傳到Linux機器，并使用“gcc -g -o StringContainsStringContains.c”命令對該程序進行編譯，生成“StringContains”文件。下面對程序進行詳細的測試。

1.輸入較長字符串為“ABCDF”、較短字符串為“AF”時，程序運行情況如下：

Please input the longer string: 
ABCDF 
LongerStr=ABCDF 
Please input the shorter string: 
AF 
ShorterStr=AF 
ABCDF contains AF!

2.輸入較長字符串為“AB”、較短字符串為“ABC”時，程序運行情況如下：

Please input the longer string: 
AB 
LongerStr=AB 
Please input the shorter string: 
ABC 
ShorterStr=ABC 
ABC is longer than AB, please check!

3.輸入較長字符串為“awe”、較短字符串為“rf”時，程序運行情況如下：

Please input the longer string: 
awe 
LongerStr=awe 
Please input the shorter string: 
rf 
ShorterStr=rf 
awe doesn't contain rf!

4.輸入較長字符串為“`11245”、較短字符串為“45”時，程序運行情況如下：

Please input the longer string: 
`11245 
LongerStr=`11245 
Please input the shorter string: 
45 
ShorterStr=45 
`11245 contains 45!

5.輸入較長字符串為“123”、較短字符串為“123 45”時，程序運行情況如下：

Please input the longer string: 
123 
LongerStr=123 
Please input the shorter string: 
123 45 
ShorterStr=123 
123 contains 123!

可見，對于上面考慮到的幾種特殊情況，程序均能做出正確的處理。

六、需求擴展

基于本文中的需求和程序，我們可考慮對需求進行以下擴展：

1.限制輸入的字符串中只能包含字母，如果包含了其它字符，則直接退出而不進行處理。

2.如果較短的字符串中的所有字符雖然都在較長的字符串中，但某個字符在較短的字符串中出現的次數大于了在較長的字符串中出現的次數，那么就認為較長的字符串不包含較短的字符串。

【本文是51CTO專欄作者周兆熊的原創文章，作者微信公眾號：周氏邏輯(logiczhou)】

戳這里，看該作者更多好文

責任編輯：趙寧寧來源： 51CTO專欄

字符串算法代碼