【字符串處理算法】獲取最長(zhǎng)公共子串的算法設(shè)計(jì)及C代碼實(shí)現(xiàn)
一、需求描述
輸入兩個(gè)字符串，編寫(xiě)程序獲取這兩個(gè)字符串的***個(gè)最長(zhǎng)公共子串。
例如，輸入的字符串為“abcdef”和“fecdba”，那么這兩個(gè)字符串的***個(gè)最長(zhǎng)公共子串為“cd”。
二、算法設(shè)計(jì)
我們可以首先尋找兩個(gè)字符串中的***個(gè)相等的字符，然后分別向后移動(dòng)來(lái)比較對(duì)應(yīng)位置的字符是否相等。
即如果字符串1為“1234abcd”，字符串2為“abd”，那么首先發(fā)現(xiàn)字符串1中的第五個(gè)字符“a”與字符串2中的***個(gè)字符“a”相等，接著字符串1中的第六個(gè)字符“b”與字符串2中的第二個(gè)字符“b”相等，再接著發(fā)現(xiàn)字符串1中的第七個(gè)字符“c”與字符串2中的第三個(gè)字符“d”不相等，此時(shí)比較結(jié)束。也就是說(shuō)字符串1和字符串2的最長(zhǎng)公共子串為“ab”。
三、特殊流程考慮
在編寫(xiě)程序的過(guò)程中，我們要對(duì)輸入的字符串的長(zhǎng)度及格式多做考慮，如：
1.如果輸入的兩個(gè)字符串之一含有中文字符，那么程序直接返回而不執(zhí)行后續(xù)流程。
2.如果輸入的兩個(gè)字符串之一含有空格，那么程序獲取空格之前的字符串進(jìn)行后續(xù)操作。
四、程序代碼
- /**********************************************************************
- * 版權(quán)所有 (C)2016, Zhou Zhaoxiong。
- *
- * 文件名稱： GetLCS.c
- * 文件標(biāo)識(shí)： 無(wú)
- * 內(nèi)容摘要： 尋找兩個(gè)字符串的最長(zhǎng)公共子串
- * 其它說(shuō)明： 例如, "abcdef"和"bcf"的最長(zhǎng)公共子串是"bc"
- * 當(dāng)前版本： V1.0
- * 作 者： Zhou Zhaoxiong
- * 完成日期： 20160322
- *
- **********************************************************************/
- #include <stdio.h>
- #include <string.h>
- #include <stdlib.h>
- // 重新定義數(shù)據(jù)類型
- typedef signed char INT8;
- typedef int INT32;
- typedef unsigned int UINT32;
- // 函數(shù)聲明
- void GetLCSOfTwoStr(INT8 *pszInputStr1, INT8 *pszInputStr2);
- /**********************************************************************
- * 功能描述： 主函數(shù)
- * 輸入?yún)?shù)： 無(wú)
- * 輸出參數(shù)： 無(wú)
- * 返 回 值： 0-執(zhí)行成功 其它-執(zhí)行失敗
- * 其它說(shuō)明： 無(wú)
- * 修改日期 版本號(hào) 修改人 修改內(nèi)容
- * ---------------------------------------------------------------------
- * 20160322 V1.0 Zhou Zhaoxiong 創(chuàng)建
- ***********************************************************************/
- INT32 main()
- {
- INT8 szInputStr1[100] = {0};
- INT8 szInputStr2[100] = {0};
- UINT32 iPosFlag = 0;
- printf("Please input string1: \n");
- scanf("%s", szInputStr1);
- printf("InputStr1=%s\n", szInputStr1);
- printf("Please input string2: \n");
- scanf("%s", szInputStr2);
- printf("InputStr2=%s\n", szInputStr2);
- // 先判斷是否有中文字符
- for (iPosFlag = 0; iPosFlag < strlen(szInputStr1); iPosFlag ++)
- {
- if (szInputStr1[iPosFlag] < 0) // 小于0則表示含有中文字符
- {
- printf("%s has Chinese character, please check!\n", szInputStr1);
- return -1;
- }
- }
- for (iPosFlag = 0; iPosFlag < strlen(szInputStr2); iPosFlag ++)
- {
- if (szInputStr2[iPosFlag] < 0) // 小于0則表示含有中文字符
- {
- printf("%s has Chinese character, please check!\n", szInputStr2);
- return -1;
- }
- }
- // 再調(diào)用函數(shù)獲取兩個(gè)字符串的最長(zhǎng)公共子串
- GetLCSOfTwoStr(szInputStr1, szInputStr2);
- return 0;
- }
- /**********************************************************************
- * 功能描述： 獲取兩個(gè)字符串的最長(zhǎng)公共子串
- * 輸入?yún)?shù)： pszInputStr1-輸入字符串1
- pszInputStr2-輸入字符串2
- * 輸出參數(shù)： 無(wú)
- * 返 回 值： 無(wú)
- * 其它說(shuō)明： 無(wú)
- * 修改日期 版本號(hào) 修改人 修改內(nèi)容
- * ---------------------------------------------------------------------
- * 20160322 V1.0 Zhou Zhaoxiong 創(chuàng)建
- ***********************************************************************/
- void GetLCSOfTwoStr(INT8 *pszInputStr1, INT8 *pszInputStr2)
- {
- UINT32 iInnerLoopFlag = 0;
- UINT32 iOutterLoopFlag = 0;
- UINT32 iPosFlag = 0;
- UINT32 iLCSLen = 0;
- INT32 iStartPos = -1;
- INT8 szLCS[100] = {0};
- if (pszInputStr1 == NULL || pszInputStr2 == NULL)
- {
- return;
- }
- for (iOutterLoopFlag = 0; iOutterLoopFlag < strlen(pszInputStr1); iOutterLoopFlag ++)
- {
- for (iInnerLoopFlag = 0; iInnerLoopFlag < strlen(pszInputStr2); iInnerLoopFlag ++)
- {
- if (pszInputStr1[iOutterLoopFlag] == pszInputStr2[iInnerLoopFlag])
- {
- for (iPosFlag = 1; pszInputStr1[iOutterLoopFlag+iPosFlag] != '\0'; iPosFlag ++)
- {
- if (pszInputStr1[iOutterLoopFlag+iPosFlag] != pszInputStr2[iInnerLoopFlag+iPosFlag]) // 遇到不相等的字符, 則退出比較
- {
- break;
- }
- }
- if (iLCSLen < iPosFlag)
- {
- iLCSLen = iPosFlag;
- iStartPos = iOutterLoopFlag;
- }
- }
- }
- }
- if (iStartPos == -1)
- {
- memset(szLCS, 0x00, sizeof(szLCS));
- }
- else
- {
- memcpy(szLCS, &pszInputStr1[iStartPos], iLCSLen);
- }
- if (iLCSLen > 0)
- {
- printf("%s和%s的最長(zhǎng)公共子串是:%s, 其長(zhǎng)度是:%d\n", pszInputStr1, pszInputStr2, szLCS, iLCSLen);
- }
- else
- {
- printf("%s和%s無(wú)公共子串!\n", pszInputStr1, pszInputStr2);
- }
- }
五、程序測(cè)試
我們將編寫(xiě)好的程序“GetLCS.c”上傳到Linux機(jī)器，并使用“gcc -g -o GetLCS GetLCS.c”命令對(duì)該程序進(jìn)行編譯，生成“GetLCS”文件。下面對(duì)程序進(jìn)行詳細(xì)的測(cè)試。
1.輸入字符串1為“abcdef”，字符串2為“hijkabm”時(shí)，程序運(yùn)行情況如下：
- Please input string1:
- abcdef
- InputStr1=abcdef
- Please input string2:
- hijkabm
- InputStr2=hijkabm
- abcdef和hijkabm的最長(zhǎng)公共子串是:ab, 其長(zhǎng)度是:2
2.輸入字符串1為“1234!@#”，字符串2為“5678!@#1”時(shí)，程序運(yùn)行情況如下：
- Please input string1:
- 1234!@#
- InputStr1=1234!@#
- Please input string2:
- 5678!@#1
- InputStr2=5678!@#1
- 1234!@#和5678!@#1的最長(zhǎng)公共子串是:!@#, 其長(zhǎng)度是:3
3.輸入字符串1為“123你們好”，字符串2為“123”時(shí)，程序運(yùn)行情況如下：
- Please input string1:
- 123你們好
- InputStr1=123你們好
- Please input string2:
- 123
- InputStr2=123
- 123你們好 has Chinese character, pleasecheck!
4.輸入字符串1為“123abc”，字符串2為“abd ef”時(shí)，程序運(yùn)行情況如下：
- Please input string1:
- 123abc
- InputStr1=123abc
- Please input string2:
- abd ef
- InputStr2=abd
- 123abc和abd的最長(zhǎng)公共子串是:ab, 其長(zhǎng)度是:2
5.輸入字符串1為“abcdef”，字符串2為“123456”時(shí)，程序運(yùn)行情況如下：
- Please input string1:
- abcdef
- InputStr1=abcdef
- Please input string2:
- 123456
- InputStr2=123456
- abcdef和123456無(wú)公共子串!
六、需求擴(kuò)展
基于本文中的需求和程序，我們可考慮對(duì)需求進(jìn)行以下擴(kuò)展：
1.如果兩個(gè)字符串有多于一個(gè)最長(zhǎng)公共子串，則都要將它們輸出，即如果字符串1為“1234abcd”，字符串2為“abd12”，那么程序輸入的最長(zhǎng)公共子串為“12”和“ab”。
2.不限制輸入字符串中不能出現(xiàn)中文字符，即如果字符串1為“我們123”，字符串2為“我們”，那么最長(zhǎng)公共子串為“我們”。
【本文是51CTO專欄作者周兆熊的原創(chuàng)文章，作者微信公眾號(hào)：周氏邏輯(logiczhou)】
