最长公共子串

博主： grinrain
发布时间：2024 年 02 月 23 日
2444次浏览
12 条评论
821字数
分类： C++

给定两个字符串，求这两个字符串的**不包含数字** 的最长公共子串的长度。

#### 输入格式

共两行，每行一个由小写字母和数字构成的字符串。

#### 输出格式

一个整数，表示给定两个字符串的**不包含数字** 的最长公共子串的长度。

如果不存在满足要求的非空公共子串，则输出 **0**0。

#### 数据范围

输入字符串的长度均不超过 **10000**10000。

#### 输入样例：

```
ab123abccff
abcfacb123
```

#### 输出样例：

```
3
```

```C++
#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

const int N = 20010, P = 131;
ull p[N], h[N];
char str[N];
int n, m;

ull get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

bool check(int mid) {
    unordered_set<ull> hash;
    for(int i = 1; i + mid - 1 <= n; i++){
        hash.insert(get(i, i + mid - 1));
    }
    
    for (int i = n + 1; i + mid - 1 <= n + m; i++) {
        if (hash.count(get(i, i + mid - 1))) return true;
    }
    return false;
}

int main() {
    cin >> str + 1;
    n = strlen(str + 1);
    cin >> str + n + 1;
    m = strlen(str + n + 1);
    
    p[0] = 1;
    for (int i = 1; i <= n + m; i++) {
        p[i] = p[i - 1] * P;
        
        char c = str[i];
        if (isdigit(c)) {
            if (i <= n) c = '#';
            else c = '$';
        }
        h[i] = h[i - 1] * P + c;
    }
    
    int l = 0, r = min(n, m);
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    
    cout << l << endl;
    
    return 0;
}
```

最后修改：2024 年 02 月 23 日 12 : 37 PM

如果觉得我的文章对你有用，请随意赞赏

12 条评论

wiucojrmae
March 2nd, 2025 at 11:35 am

对国际规则的解读具有前瞻性。

回复
gcbualrjqu
January 3rd, 2025 at 05:17 am

《两个遥远的陌生人》剧情片高清在线免费观看：https://www.jgz518.com/xingkong/12436.html

回复
jylqibmrdc
December 9th, 2024 at 06:38 am

《连环杀局1风云花戏楼》动作片高清在线免费观看：https://www.jgz518.com/xingkong/22447.html

回复
kyddylkwmy
December 3rd, 2024 at 07:32 pm

每次看到你的文章，我都觉得时间过得好快。 https://www.4006400989.com/qyvideo/86719.html

回复
dwqfpdkebh
November 30th, 2024 at 08:20 am

《连环杀局1风云花戏楼》动作片高清在线免费观看：https://www.jgz518.com/xingkong/22447.html

回复
sauggfdoer
November 28th, 2024 at 11:53 pm

你的文章让我感受到了无尽的欢乐，谢谢分享。 https://www.yonboz.com/video/65275.html

回复
zxxwugrqba
November 15th, 2024 at 05:53 pm

你的文章内容非常精彩，让人回味无穷。 https://www.4006400989.com/qyvideo/78579.html

回复
dellkjvafd
November 13th, 2024 at 04:05 am

破解玩传奇私服卡顿之谜：揭秘背后惊天秘密，告别游戏延迟！：https://501h.com/fugu/2024-07-31/24529.html

回复
mspjrngnbp
October 4th, 2024 at 09:55 pm

不错不错，我喜欢看 https://www.ea55.com/

回复
yunufzfbmt
October 1st, 2024 at 09:24 pm

想想你的文章写的特别好https://www.237fa.com/

回复
ndlhknnqmn
September 27th, 2024 at 01:31 pm

怎么收藏这篇文章？

回复
djstsvloop
September 23rd, 2024 at 06:43 am

叼茂SEO.bfbikes.com

回复