找出多个字符串中的最大公共子字符串用什么方法?{:2_41:}

N个字符串的最大公共子串：

整个程序的思路如下：

第一步，首先从所有的输入参与匹配的字符串中，选出长度最小的串放在字符串数组中第一的位置，swap函数就是用于交换的

第二步，拿长度最小的字符串开刀，两个for循环用于控制并求出最小字符串的子串，比如对bbcdef，子串序列是bbcdef、bbcde、bbcd、bbc、bb⋯⋯

如果剩余的的长度小于maxlen则没必要继续求下去了，详情见两个for循环

第三步，对于求出来的每个子串，与剩余的参与匹配的字符串匹配，利用字符串自带的find函数来确定tmpStr是否是剩余字符串的子串。以此来找出最大的公共子串。



源代码：

#include <iostream>
#include <string>

using namespace std;

//将第一个字符串与最短的字符串交换
void swap(string *pStr,int i)
{
    string temp;
    temp = *pStr;
    *pStr = *(pStr + i);
    *(pStr + i) = temp;
}

int main()
{
    int N;
   
    cout << "请输入N(控制字符串个数):";
    cin >> N;

    cout << "请输入" << N << "个字符串"<<endl;

    string *pStr;
    pStr = new string [N];
    int i,min;
    int maxLen = 1000;
    //找出输入的字符串中长度最小的串，并把最小串序号记在min中
    for(i = 0; i < N; ++i){
        cin >> *(pStr + i);
        int len = (*(pStr +i)).length();// *操作符与调用函数的.操作符优先级问题，.优先级高于*，所以必须加上()
        if(len < maxLen){
            maxLen = len;
            min = i;
        }
    }
    swap(pStr,min);
    /*
    for(i = 0; i < N; ++i)
        cout << *(pStr + i) << endl;
    */
   
    int len0 = pStr[0].length();
    int j,k,maxlen= 0;
    string maxStr;
    string tmpStr;
    for(i = 0; i < len0 && maxlen <= len0 - i -1; ++i)
    {
        for(j = 0; j < len0 && maxlen <= len0 - i -j - 1; ++j)
        {
            tmpStr = pStr[0].substr(i,len0 - j);//对字符串数组中第一个子串，求出其可能的子串值，如果剩余子串长度小于maxlen则不用去求了，for循环中给出了限制
            //将子串tmpStr与参与匹配的字符串比较，判断tmpStr是否为剩余串的子串，如果不是则break出循环
            for(k = 1; k < N; ++k)
            {
                string::size_type pos1 = pStr[k].find(tmpStr);
                if(pos1 < pStr[k].length())
                    continue;
                else
                    break;
            }
            if(k == N)//说明子串tmpStr是其他参与匹配的子串的子串
            {
                if(tmpStr.length() > maxlen)//tmpStr如果是当前最大的子串，则记录下来
                {
                    maxlen = tmpStr.length();
                    maxStr = tmpStr;
                }
            }
        }
    }
    cout << "最大公共子串为：";
    cout << maxStr <<endl;
    delete []pStr;
    return 0;
}