A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© x331275955 中级黑马   /  2015-8-18 23:16  /  2814 人查看  /  1 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

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

最佳答案

查看完整内容

N个字符串的最大公共子串: 整个程序的思路如下: 第一步,首先从所有的输入参与匹配的字符串中,选出长度最小的串放在字符串数组中第一的位置,swap函数就是用于交换的 第二步,拿长度最小的字符串开刀,两个for循环用于控制并求出最小字符串的子串,比如对bbcdef,子串序列是bbcdef、bbcde、bbcd、bbc、bb⋯⋯ 如果剩余的的长度小于maxlen则没必要继续求下去了,详情见两个for循环 第三步,对于求出来的每个子串,与剩余的 ...

1 个回复

倒序浏览
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;
}
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马