最长公共子序列+最长公共子串+编辑距离

最长公共子序列

利用二维数组f[i][j]，表示a[1~i]和 b[1 ~j]的最长公共子序列的长度
边界条件:f[0][j]=0,f[i][0]=0
获取lcs的长度:

int n,m,f[1005][1005];
string s1,s2;
void lcs()
{
    n=s1.length();
    m=s2.length();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(s1[i-1]==s2[j-1])
                f[i][j]=f[i-1][j-1]+1;
            else 
                f[i][j]=max(f[i-1][j],f[i][j-1]);
        }
    }
    cout<<f[n][m]<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

获取最长公共子序列的值:

int n,m,f[1005][1005],p[1005][1005];
string s1,s2;
void lcs()
{
    n=s1.length();
    m=s2.length();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(s1[i-1]==s2[j-1])
            {
                f[i][j]=f[i-1][j-1]+1;
                p[i][j]=1;  //左上方
            }
            else if(f[i][j-1]>f[i-1][j])
            {
                f[i][j]=f[i][j-1];
                p[i][j]=2;  //左边
            }
            else
            {
                f[i][j]=f[i-1][j];
                p[i][j]=3;  //上边
            }
        }
    }
    cout<<f[n][m]<<endl;
}
void get_lcs()
{
    char c[1005];
    i=n,j=m,k=f[n][m];
    while(i>0&&j>0)
    {
        if(p[i][j]==1)
        {
            s[k--]=a[i-1];i--,j--;
        }
        else if(p[i][j]==2)
            j--;
        else 
            i--;
    }
}
void solve()
{
    lcs();
    get_lcs();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

最长公共子串

不同点在于子序列不必要连续，而子串必须要连续。
因此只有当两字符串中的字符连续相等时，公共子串的长度才会不断累加，否则清零。
状态变量：f[i][j]表示已a[i]和b[j]为结尾的公共子串的长度
代码：

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=1e6+7;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
int n,m,f[1005][1005],p[1005][1005];
string s1,s2;
void lcs()
{
    n=s1.length();
    m=s2.length();
    int mx=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(s1[i-1]==s2[j-1])
                f[i][j]=f[i-1][j-1]+1;
            else 
                f[i][j]=0;
            mx=max(mx,f[i][j]);
        }
    }
    cout<<mx<<endl;
}

void solve()
{
    lcs();
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

编辑距离

通过增删改操作使得两个字符串相等的最少操作次数
时间、空间复杂度：O(m*n)

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=1e6+7;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
int n,m,f[1005][1005],p[1005][1005];
string s1,s2;
void lcs()
{
    n=s1.length();
    m=s2.length();
    for(int i=1;i<=n;i++)   f[i][0]=i;
    for(int i=1;i<=m;i++)   f[0][i]=i;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(s1[i-1]==s2[j-1])
                f[i][j]=f[i-1][j-1];
            else 
                f[i][j]=min({f[i-1][j-1],f[i-1][j],f[i][j-1]})+1;
                            //  修改      删除      插入
        }
    }
    cout<<f[n][m]<<endl;
}

void solve()
{
    lcs();
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

进行空间优化,利用滚动数组，将为O(n)(有点没听懂,先记录下):
https://www.bilibili.com/video/BV1gk4y1177j?spm_id_from=333.999.0.0&vd_source=91973ada1213cf6ba2cbb43a2bebd2e8