最长公共连续子串

谁借莪１个温暖的怀抱￠ 2023-07-03 07:23 13阅读 0赞

给出两个字符串（可能包含空格）,找出其中最长的公共连续子串,输出其长度。

**输入描述:**

输入为两行字符串（可能包含空格），长度均小于等于50.

**输出描述:**

输出为一个整数，表示最长公共连续子串的长度。

**示例1**

**输入**

abcde
    abgde

**输出**

方法一：

输入的两个字符串为s1, s2。申请一个二维数组num\[row\]\[col\]，行数row等于s1.size()，列数col等于s2.size()。

num\[i\]\[j\]表示s1的第i个字符和s2的第j个字符是否相等，0表示不相等，1表示相等。

最后遍历二维数据，找出斜线上连续1的最大个数。

#include<iostream>
    #include<vector>
    #include<string>
    using namespace std;
    int GetSubStr(const string&s1, const string&s2){
        vector<vector<int>> num;
        num.resize(s1.size());
        for (int i = 0; i < s1.size(); i++){
            for (int j = 0; j < s2.size(); j++){
                if (s1[i] == s2[j]){
                    num[i].push_back(1);
                }
                else{
                    num[i].push_back(0);
                }
            }
        }     
        int maxLen = 0;
        int index = 0;
        for (int i = 0; i < s1.size(); i++){
            for (int j = 0; j < s2.size(); j++){
                int m = i;
                int n = j;
                int count=0;
                while (m < s1.size() && n < s2.size()&& num[m++][n++] == 1){
                    count++;
                }
                if (count > maxLen){
                    maxLen = count;
                    index = i;
                }
            }
        }   
        return maxLen;
    }
    int main(){
        int n;
        string s1, s2;
        while (getline(cin, s1) && getline(cin, s2)){
            int res = GetSubStr(s1,s2);
            cout << res << endl;
        }
    }