题解 | #公共子串计算#

公共子串计算

https://www.nowcoder.com/practice/98dc82c094e043ccb7e0570e5342dd1b

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

int get(string& s, string& t, int a, int b) {
    int i = a;
    int j = b;
    int cur = 0;
    int res = 0;
    while(i < s.length() && j < t.length()) {
        if(s[i++] == t[j++]) {
            cur++;
            res = max(cur, res);
            continue;
        }
        cur = 0;
    }
    return res;
}
int main() {
    string s;
    string t;
    cin >> s;
    cin >> t;
    int i = s.size() - 1;
    int j = 0;
    int res = 0;
    while(i >= 0) {
        res = max(get(s, t, i--, j), res);
    }
    i++;
    while(j < t.length()) {
        res = max(get(s, t, i, j++), res);
    }
    cout << res << endl;
    return 0;
}

两把尺子对齐,双指针,这种方法好像在哪里见到过,映像中是leetcode做过。

全部评论

相关推荐

07-02 18:09
门头沟学院 Java
苍穹外卖和谷粒商城这俩是不是烂大街了,还能做吗?
想去重庆的鸽子在吐槽:你不如把这俩做完自己搞明白再优化点再来问 何必贩卖焦虑
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务