最长公共子串计算C++

秒速五厘米 2022-05-10 01:42 203阅读 0赞

**公共字串计算（最长公共子串/序列）C++**

### 描述 ###

> 题目标题：  
> 计算两个字符串的最大公共字串的长度，字符不区分大小写

### 输入 ###

> 输入两个字符串

### 输出 ###

> 输出一个整数

### 样例输入 ###

> asdfas werasdfaswer

### 样例输出 ###

> 6

## 思路 ##

暴力求解  
此题用cin即可

## 代码 ##

#include <iostream>
    #include <string>
    using namespace std;
    int Maxsubstr(string a,string b)
    {
        unsigned int start1,start2;
        int count=0,Max=0;
        for(unsigned int i=0; a[i]!='\0'; i++)
        {
            for(unsigned int j=0; b[j]!='\0'; j++)
            {
                start1=i;
                start2=j;
                while(a[start1]==b[start2] && start1<a.length() && start2<b.length())
                {
                    start1++;
                    start2++;
                    count++;
                }
                if(count>Max)
                {
                    Max=count;
                }
                count=0;
            }
        }
        return Max;
    }
    
    int main()
    {
        string str1,str2;
        cin>>str1;
        cin>>str2;
        //不区分大小写
        for (unsigned int i=0; i<str1.length(); i++)
        {
            str1[i]=tolower(str1[i]);
        }
        for (unsigned int i=0; i<str2.length(); i++)
        {
            str2[i]=tolower(str2[i]);
        }
        cout<<Maxsubstr(str1,str2)<<endl;
    }

![这里写图片描述][20170102161722664]

## 题目 ##

### 描述 ###

> 查找两个字符串a,b中的最长公共子串。  
> 详细描述：  
> 查找两个字符串a,b中的最长公共子串。

### 输入 ###

> 输入两个字符串

### 输出 ###

> 返回重复出现的字符

### 样例输入 ###

> abcdefghijklmnop  
> abcsafjklmnopqrstuvw

### 样例输出 ###

> jklmnop

## 思路 ##

暴力求解

## 代码 ##

#include <iostream>
    #include <string>
    using namespace std;
    int Maxsubstr(string a,string b,string *&s)
    {
        unsigned int start,start1,start2;
        int count=0,Max=0;
        for(unsigned int i=0; a[i]!='\0'; i++)
        {
            for(unsigned int j=0; b[j]!='\0'; j++)
            {
                start1=i;
                start2=j;
                while(a[start1]==b[start2] && start1<a.length() && start2<b.length())
                {
                    start1++;
                    start2++;
                    count++;
                }
                if(count>Max)
                {
                    start = i;
                    Max = count;
                }
                count=0;
            }
        }
        //保存字符串
        s=new string[Max+1];
        for(int i=0; i<Max; i++)
        {
            s[i]=a[i+start];
        }
        s[Max]='\0';
        return Max;
    }
    
    int main()
    {
        string str1,str2,*str;    
        cin>>str1>>str2;
        //此题输入-------------
        //getline(cin,str1);
        //getline(cin,str2);
        int length = Maxsubstr(str1,str2,str);
        for(int i=0; i<length; i++)
        {
            cout<<str[i];
        }
        cout<<endl;
        return 0;
    }

> 如果你看到这里觉得**暴力方法**太**low**
> 
> ### Low。。。。 ###

哎，那就聊聊动态规划版的经典问题《最长公共子串（序列）》

**子串是连续的，子序列可以是不连续的。**

状态转移方程：

> 符号约定，C1是S1的最右侧字符，C2是S2的最右侧字符，S1‘是从S1中去除C1的部分，S2’是从S2中去除C2的部分。

LCS(S1,S2)等于下列3项的最大者：

> （1）LCS（S1，S2′′）

（2）LCS（S1′′，S2）

（3）LCS（S1′′）+C1 —如果C1等于C2；

边界终止条件：如果S1和S2都是空串，则结果也是空串。

下面我们同样要构建一个矩阵来存储动态规划过程中子问题的解。这个矩阵中的每个数字代表了该行和该列之前的LCS的长度。与上面刚刚分析出的状态转移议程相对应，矩阵中每个格子里的数字应该这么填，它等于以下3项的最大值：

（1）上面一个格子里的数字

（2）左边一个格子里的数字

（3）左上角那个格子里的数字（如果 C1不等于C2）； 左上角那个格子里的数字+1（ 如果C1等于C2）

#include<iostream>
    #include<cstring>
    #include <vector>
    
    using namespace std;
    
    void SubSequence(vector<vector<string>> &flag,string str1, string str2,int i,int j);
    void display(int *result,string str1,string str2);
    
    void initialVector(vector<vector<string>> &vectorAll,int len)
    {
        for(int i=0; i<len; ++i)
        {
            vector<string> temp;
            vectorAll.push_back(temp);
        }
    }
    
    int lcs_string(string str1, string str2)
    {
        int len1 = str1.length();
        int len2 = str2.length();
        int result = 0;     //记录最长公共子串长度
        int c[len1+1][len2+1] ;
        int endPos = -1;
        for (int i = 0; i <= len1; i++)
        {
            for( int j = 0; j <= len2; j++)
            {
                if(i == 0 || j == 0)
                {
                    c[i][j] = 0;
                }
                else if (str1.at(i-1) == str2.at(j-1))
                {
                    c[i][j] = c[i-1][j-1] + 1;
                    result = max(c[i][j], result);
                    if(result==c[i][j])  endPos = i;//记录最后一个点的位置
                }
                else
                {
                    c[i][j] = 0;//重新计数
                }
            }
        }
        //print result
        string str="";
        if(endPos<=len1)
        {
            str = str1.substr(endPos-result,result);
        }
        else
        {
            str = str2.substr(endPos-result,result);
        }
        cout<<"\n\nLongest Common Substring : "<<str<<endl;
        return result;
    }
    //对于最长公共子序列，只是在最后一个else里面放的是前两步的最大值
    int lcs_squence(string str1, string str2)
    {
        int len1 = str1.length();
        int len2 = str2.length();
        int c[len1+1][len2+1];
        vector<vector<string>> flag;
        initialVector(flag,len1+1);
        for (int i = 0; i <= len1; i++)
        {
            for( int j = 0; j <= len2; j++)
            {
                if(i == 0 || j == 0)
                {
                    c[i][j] = 0;
                    flag[i].push_back("NULL");
                }
                else if (str1.at(i-1) == str2.at(j-1))
                {
                    c[i][j] = c[i-1][j-1] + 1;
                    flag[i].push_back("left_up");
    
                }
                else if(c[i - 1][j]>=c[i][j - 1])
                {
                    c[i][j]=c[i - 1][j];
                    flag[i].push_back("left");
                }
                else
                {
                    c[i][j] = c[i][j - 1];
                    flag[i].push_back("up") ;
                }
            }
    
        }
        //display(&c[0][0],str1,str2); //输出数组
        SubSequence(flag,str1,str2,str1.length(),str2.length());
        //cout<<c[len1][len2]<<endl;
        return c[len1][len2];
    }
    
    void display(int *result,string str1,string str2)
    {
        int len1 = str1.length();
        int len2 = str2.length();
        //输出表头
        for(int i=0; i<=len2; ++i)
        {
            cout<<"\t"<<str2[i];
        }
        cout<<endl;
        //输出数组
        for(int i=0; i<=len1; ++i)
        {
            cout<<str1[i]<<"\t";
            for(int j=0; j<=len2; ++j)
            {
                cout<<*result<<"\t";
                result++;
            }
            cout<<endl;
        }
    
    }
    //按照方向查找
    void SubSequence(vector<vector<string>> &flag,string str1, string str2,int i,int j)
    {
        if (i == 0 || j == 0)
            return;
    
        if (flag.at(i).at(j) == "left_up")
        {
            cout<<str2[j - 1]<<" ("<< i - 1<<" , "<< j - 1<<")"<<endl;
            //左前方
            SubSequence(flag,str1,str2,i - 1, j - 1);
        }
        else
        {
            if (flag.at(i).at(j) == "up")
            {
                SubSequence(flag,str1,str2,i, j - 1);
            }
            else
            {
                SubSequence(flag,str1,str2,i - 1, j);
            }
        }
    }
    
    int main()
    {
        string X = "";
        string Y = "";
        //输入
        getline(cin,X);
        getline(cin,Y);
        cout<<"\nFirst string:\n"<<X<<endl;
        cout<<"\nSecond string:\n"<<Y<<endl;
        cout << "Length of Longest Common Substring is " << lcs_string(X, Y)<<endl;
        cout << "Length of Longest Common Subsequence is " << lcs_squence(X, Y)<<endl;
        return 0;
    }

![这里写图片描述][20170102165057387]

## 参考引用 ##

传送门 ： [最长公共子序列][Link 1]

传送门 ： [最长公共子序列（LCS）C++实现][LCS_C]

传送门 ： [最长公共子序列与最长公共子串][Link 2]

传送门 ： [最长公共子序列。。][Link 3]

传送门 ： [最长公共子序列。。大杂烩][Link 4]

[20170102161722664]: /images/20220510/0d2165d6a16d40518cd318d86ea7ada0.png
[20170102165057387]: /images/20220510/dd3e309cc0fe432982f4a61026594e3d.png
[Link 1]: http://www.cnblogs.com/huangxincheng/archive/2012/11/11/2764625.html
[LCS_C]: http://blog.csdn.net/alps1992/article/details/47923041
[Link 2]: http://www.cnblogs.com/en-heng/p/3963803.html
[Link 3]: http://blog.csdn.net/kingwolfofsky/article/details/39297275
[Link 4]: http://www.cnblogs.com/zhangchaoyang/articles/2012070.html