题目描述

输入两个字符串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;
}
分类: Hash

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status