2022.10.12.-秋招-第一题-D路通信

TaZi SU @ 8 months ago

思路

最长公共子串

简化题意

给定两个字符串 $s$ 和 $t$ ，问两个字符串的最长公共子串长度。

$s$ 的长度为 $n$ ， $t$ 的长度为 $m$

暴力做法

枚举 $t$ 的每个子串是否在 $s$ 中找到，即朴素的字符串匹配算法，每次匹配是 $O(nm)$ 的。枚举每个 $t$ 的子串，则是以 $t$ 的每个索引开始，依次和 $s$ 进行比较，如果存在 $t$ 的某个字符和对应的 $s$ 的字符不匹配了，则说明后续也不会匹配了，这样的复杂度为 $O(nm^2)$ 。

优化暴力做法

$dp[i][j]$ 表示以 $s[i]$ 和 $t[j]$ 结尾的子字符串的相同的最大长度。如果 $dp[i][j]=k(k\geq 1)$ ，必然有 $s[i-k+1]=t[j-k+1],s[i-k+2]=t[j-k+2],\cdots s[i]=t[j]$。故 $dp[i][j]$ 是从 $dp[i-1][j-1]$ 转移而来的。

状态转移方程为： $dp[i][j]=dp[i-1][j-1]+1$

最后取所有 $dp[i][j]$ 的 $\max$ 即可。

类似题目推荐

LeetCode

Codefun2000

代码

CPP

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int f[N][N];
char s[N], t[N];
int ns, nt;

int main()
{
    scanf("%s%s", s + 1, t + 1);
    ns = strlen(s + 1), nt = strlen(t + 1);

    // 最长公共子串

    int ans = 0;
    // 枚举 s 中子串的最后一个字符
    for (int i = 1; i <= ns; ++i) {
        // 枚举 t 中子串的最后一个字符
        for (int j = 1; j <= nt; ++j) {
            // 如果两个尾字符相等，才会有长度至少为 1 的公共子串
            if (s[i] == t[j]) {
                // 状态转移
                f[i][j] = f[i - 1][j - 1] + 1;
                // 更新答案
                ans = max(ans, f[i][j]);
            }
        }
    }

    printf("%d\n", ans);
}

python

N = 1010
f = [[0]*N for _ in range(N)]
s = input().strip()
t = input().strip()
ns, nt = len(s), len(t)

# 最长公共子串

ans = 0
# 枚举 s 中子串的最后一个字符
for i in range(1, ns+1):
    # 枚举 t 中子串的最后一个字符
    for j in range(1, nt+1):
        # 如果两个尾字符相等，才会有长度至少为 1 的公共子串
        if s[i-1] == t[j-1]:
            # 状态转移
            f[i][j] = f[i-1][j-1] + 1
            # 更新答案
            ans = max(ans, f[i][j])

print(ans)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = 1010;
        int[][] f = new int[N][N];
        char[] s = scan.next().toCharArray();
        char[] t = scan.next().toCharArray();
        int ns = s.length, nt = t.length;

        // 最长公共子串

        int ans = 0;
        // 枚举 s 中子串的最后一个字符
        for (int i = 1; i <= ns; ++i) {
            // 枚举 t 中子串的最后一个字符
            for (int j = 1; j <= nt; ++j) {
                // 如果两个尾字符相等，才会有长度至少为 1 的公共子串
                if (s[i-1] == t[j-1]) {
                    // 状态转移
                    f[i][j] = f[i - 1][j - 1] + 1;
                    // 更新答案
                    ans = Math.max(ans, f[i][j]);
                }
            }
        }

        System.out.println(ans);
    }
}

Go

package main

import (
    "fmt"
)

func main() {
    const N int = 1010
    var f [N][N]int
    var s, t string
    fmt.Scan(&s, &t)
    ns, nt := len(s), len(t)

    // 最长公共子串

    ans := 0
    // 枚举 s 中子串的最后一个字符
    for i := 1; i <= ns; i++ {
        // 枚举 t 中子串的最后一个字符
        for j := 1; j <= nt; j++ {
            // 如果两个尾字符相等，才会有长度至少为 1 的公共子串
            if s[i-1] == t[j-1] {
                // 状态转移
                f[i][j] = f[i-1][j-1] + 1
                // 更新答案
                if f[i][j] > ans {
                    ans = f[i][j]
                }
            }
        }
    }

    fmt.Println(ans)
}

Js

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
    input += data;
    return;
});
process.stdin.on('end', () => {
    const lines = input.trim().split('\n');
    const N = 1010;
    const f = new Array(N).fill().map(() => new Array(N).fill(0));
    const s = lines[0];
    const t = lines[1];
    const ns = s.length, nt = t.length;

    // 最长公共子串

    let ans = 0;
    // 枚举 s 中子串的最后一个字符
    for (let i = 1; i <= ns; ++i) {
        // 枚举 t 中子串的最后一个字符
        for (let j = 1; j <= nt; ++j) {
            // 如果两个尾字符相等，才会有长度至少为 1 的公共子串
            if (s[i-1] == t[j-1]) {
                // 状态转移
                f[i][j] = f[i - 1][j - 1] + 1;
                // 更新答案
                ans = Math.max(ans, f[i][j]);
            }
        }
    }

    console.log(ans);
});

ID

Time

1000ms

Memory

256MiB

Difficulty

Tags

动态规划

# Submissions

178

Accepted

Uploaded By

TaZi

1 solutions

思路

最长公共子串

类似题目推荐

LeetCode

Codefun2000

代码

CPP

python

Java

Go

Js

Information

Status

Development

Support