GESP 1-4级 -- GESP 5-8级 -- CSP-J/S --

A43445. $找公共子串分行输入两个字符串（2<=字符串长度<=100），找出两个字符串中最大的公共子串，然后将公共子串及公共子串的长度分行输出例如：输入两个宇串为abcdab和baabcd，其最大的公共子串为"abcd"，子串长度为4.输入描述第一行输入一个字符串第二行输入一个字符串输出描述第一行输出最大公共子串第二行输出最大公共子串长度样例输入abcdabbaabcd样例输出abcd4$

填空题困难

知识点

字符串处理最长公共子串动态规划

题目描述

找公共子串 分行输入两个字符串（2<=字符串长度<=100），找出两个字符串中最大的公共子串，然后将公共子串及公共子串的长度分行输出 例如：输入两个宇串为abcdab和baabcd，其最大的公共子串为 "abcd"，子串长度为4. 输入描述 第一行输入一个字符串 第二行输入一个字符串 输出描述 第一行输出最大公共子串 第二行输出最大公共子串长度 样例输入 abcdab baabcd 样例输出 abcd 4

参考答案

#include <bits/stdc++.h>
using namespace std;
string a, b;
int main() {
  cin >> a >> b;
  for (int l = a.size(); l >= 1; l--) {
    for (int i = 0; i <= a.size() - l; i++) {
      if (b.find(a.substr(i, l)) < b.size()) {
        cout << a.substr(i, l) << endl;
        cout << l;
        return 0;
      }
    }
  }
  return 0;
}

答案解析

// 参考代码2#include <bits/stdc++.h>using namespace std;string s1, s2;int st, len;int main() {  ios::sync_with_stdio(0);  cin.tie(0);  cin >> s1 >> s2;  int l1 = s1.size(), l2 = s2.size();  for (int i = 0; i < l1; ++i) {    for (int j = 0; j < l2; ++j) { for (int k = 1; i + k - 1 < l1 && j + k - 1 < l2; ++k) {        if (s1[i + k - 1] != s2[j + k - 1])          break;        if (k > len) {          len = k;          st = i;        }      }    }  }  for (int i = 0; i < len; ++i)    cout << s1[i + st];  cout << '\n' << len << '\n';  return 0;}评分标准：10分：能正确输出一组数据；20分：能正确输出两组数据；20分：能正确输出三组数据；

上一题下一题