最长连续公共子序列-西安电子科技大学

转载

2023 年 08 月 09 日

500 次浏览

暂无评论

657字数

算法类

[来自KeChang](https://blog.silvery.me/)

### 题目描述

输入两个字符串s1和s2，输出最长连续公共子串的长度和最长连续公共子串。

### 输入格式

一行，两个字符串s1和s2，用空格隔开。

### 输出格式

第一行输出最长连续公共子串的长度。

第二行输出最长连续公共子串。如果不唯一，则输出s1中的最后一个。

### 数据范围

1≤|s1|,|s2|≤100

数据保证至少存在一个连续公共子串。

### 输入样例：

```
abcdefg qwercdefiok
```

### 输出样例：

```
4
cdef
```

### 题目分析

字符串哈希表 暴力枚举 ~KMP~

### 代码实现

```
#include <iostream>
#include <unordered_set>
#include <cstring>
using namespace std;
const int N = 1e2 + 10;

string s1, s2, res;
unordered_set <string> st;
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> s1 >> s2;
    for (int i = 0; i < s1.length(); ++i) {
        for (int j = 0; j <= i; ++j) {
            st.insert(s1.substr(j, i - j + 1));
        } 
    }
    for (int i = 0; i < s2.length(); ++i) {
        for (int j = 0; j <= i; ++j) {
            if (res.length() <= i - j + 1) {
                string ans = s2.substr(j, i - j + 1);
                if (st.find(ans) != st.end()) {
                    res = ans;       
                }    
            }
        } 
    }
    cout << (int)res.length() << '\n' << res;
    return 0;
}
```

~还有脑抽了写的KMP~

```
#include <iostream>
#include <unordered_map>
#include <cstring>
using namespace std;
const int N = 1e2 + 10;

string s1, s2, ans;
unordered_map <string,bool> mp;
bool kmp(string& p, const string& s) {
    int n = p.length(), m = s.length() - 1, ne[N];
    memset(ne, 0, sizeof ne);
    p = ' ' + p;
    for (int i = 2, j = 0; i <= n; ++i) {
        while(j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) ++j;
        ne[i] = j;
    }
    for (int i = 1, j = 0; i <= m; ++i) {
        while(j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) ++j;
        if (j == n) return true;
    }
    return false;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> s1 >> s2;
    s2 = ' ' + s2;
    for (int i = 0; i < (int)s1.length(); ++i) {
        for (int j = 0; j <= i; ++j) {
            if ((int)ans.length() <= i - j + 1) {
                string sub = s1.substr(j,i - j + 1);
                if (mp.find(sub) == mp.end()) {
                    mp[sub] = 1;
                    if (kmp(sub,s2)) {  
                        ans = sub.substr(1); 
                    }
                }    
            }
            else break;
        }
    }
    cout << (int)ans.length() << '\n' << ans;
    return 0;
}
```

最后修改：2023 年 08 月 09 日