[daily practice] day (14)

---

One 、 choice question

eg1

eg2

eg3

eg4

eg4

eg5

eg6

eg7

eg8

eg9

eg10

eg11

eg12

eg13

eg14

Two 、 Programming questions

eg1

【 Their thinking 】：
This problem needs to be solved by dynamic programming ,MCS[i][j] Record short string s1 front i Characters and long strings s2 front j The length of the longest substring of characters , Initialize all values to 0. When s1[i-1] = s2[j-1] when ,MCS[i][j] = MCS[i - 1][j - 1] + 1, Here we use an extra value start To record the longest substring in a short string s1 The starting position in ,maxlen Record the length of the current longest substring , When MCS[i][j] >maxlen when ,maxlen = MCS[i][j], be start = i - maxlen ; files s1[i-1] != s2[j-1] No operation is required , Finally get substr(start, maxlen) It's what you want

#include <iostream>
#include <string>
#include <vector>
using namespace std;

string GetSubStr(string& s1, string& s2)
{
    
    if(s1.size() > s2.size())
        swap(s1, s2);
    int len1 = s1.size();
    int len2 = s2.size();
    // Open up one more row and one more column , Initialize to 0
    vector<vector<int>> MSC(len1+1, vector<int>(len2+1, 0));
    int max_size = 0;
    int start = 0;
    for(int i = 1; i < len1; ++i)
    {
    
        for(int j  = 1; j < len2; ++j)
        {
    
            if(s2[j-1] == s1[i-1])
                MSC[i][j] = MSC[i-1][j-1] + 1;
            if(MSC[i][j] > max_size)
            {
    
                max_size = MSC[i][j];
                start = i - max_size;
            }
        }
    }
    return s1.substr(start, max_size);
}

int main()
{
    
    string s1;
    string s2;
    while(cin >>s1 >> s2)
    {
    
        string ret = GetSubStr(s1, s2);
        cout << ret << endl;
    }
    return 0;
}