给两条线 A. 和 B 。任务是计算在字符串a中插入字符的方法数，以将字符串a和字符串B之间最长公共子序列的长度增加1。 例如：
null
输入：A=“aa”，B=“baaa” 产出：4 字符串A和字符串B共享的最长公共子序列是“aa”，其长度为2。 有两种方法可以通过向字符串a添加单个字符将最长公共子序列的长度增加到3：
- 字符串A中有3个不同的位置，我们可以在其中插入一个额外的“A”，以创建最长的公共子序列“aaa”（即在字符串的开头、中间和结尾）。
- 我们可以在字符串的开头插入一个“b”，表示新的最长公共子序列“baaa”。因此，我们有3+1=4种方法将字母数字字符插入字符串A，并将最长公共子序列的长度增加1。
假设对于给定的字符串a和字符串B，它们的长度 LCS 是 K .让我们在字符串a的第i个字符后插入一个字符“c”，并将插入后形成的字符串表示为字符串a 新 ，看起来像： A. 新 =A 1.我 CA. i+1，n 哪里 i、 j 表示从第i个字符到第j个字符和“.”的字符串a的子字符串表示两个字符串的串联。 让我们定义k 新 为一个 新 B.现在我们想知道k 新 =k+1。 关键的观察是，新插入的字符“c”必须是a的任何公共子序列的一部分 新 长度大于k的B。我们知道这一点，因为如果A有任何公共子序列 新 这是一个矛盾，因为这意味着a和B的LCS的长度大于k。 根据以上观察，我们可以尝试以下方法。对于每个可能的字符“c”（有52个大写和小写英文字母和10个阿拉伯数字，因此有62个可能的字符要插入），对于字符串A中的每个可能的插入i（有| A |+1个插入位置），让我们尝试在字符串A中的第i个字符后插入“c”，并将其与字符串B中出现的每个“c”匹配，我们可以尝试匹配这些“c”字符，以便： A. 1.我 CA. i+1，n B 1，j-1 CB j+1，m 现在，为了检查这样的插入是否产生长度为k+1的LCS，只需检查 1.我 B 1，j-1 加上LCS A的长度 i+1，n B j+1，m 等于k。在这种情况下，A的lCS 新 B是k+1，因为字符“c”的固定出现之间存在匹配，并且它们之间不再有公共子序列。 如果我们能快速得到A和B的每两个前缀之间以及它们的每两个后缀之间的LCS的长度，我们就能计算出结果。前缀之间的LCS长度可以从用于计算字符串a和字符串B的LCS的动态规划表中读取。在这种方法中，dp[i][j]存储字符串a的最长公共子序列的长度 我 B i、 j .类似地，后缀之间的LCS长度可以从类似的dp表中读取，该dp表可以在计算 颠倒的 B 颠倒的 在哪里 颠倒的 表示反向字符串S。
C++
// CPP Program to Number of ways to insert a // character to increase LCS by one #include <bits/stdc++.h> #define MAX 256 using namespace std; // Return the Number of ways to insert a // character to increase the Longest // Common Subsequence by one int numberofways(string A, string B, int N, int M) { vector< int > pos[MAX]; // Insert all positions of all characters // in string B. for ( int i = 0; i < M; i++) pos[B[i]].push_back(i + 1); // Longest Common Subsequence int dpl[N + 2][M + 2]; memset (dpl, 0, sizeof (dpl)); for ( int i = 1; i <= N; i++) { for ( int j = 1; j <= M; j++) { if (A[i - 1] == B[j - 1]) dpl[i][j] = dpl[i - 1][j - 1] + 1; else dpl[i][j] = max(dpl[i - 1][j], dpl[i][j - 1]); } } int LCS = dpl[N][M]; // Longest Common Subsequence from reverse int dpr[N + 2][M + 2]; memset (dpr, 0, sizeof (dpr)); for ( int i = N; i >= 1; i--) { for ( int j = M; j >= 1; j--) { if (A[i - 1] == B[j - 1]) dpr[i][j] = dpr[i + 1][j + 1] + 1; else dpr[i][j] = max(dpr[i + 1][j], dpr[i][j + 1]); } } // inserting character between position // i and i+1 int ans = 0; for ( int i = 0; i <= N; i++) { for ( int j = 0; j < MAX; j++) { for ( auto x : pos[j]) { if (dpl[i][x - 1] + dpr[i + 1][x + 1] == LCS) { ans++; break ; } } } } return ans; } // Driver Program int main() { string A = "aa" , B = "baaa" ; int N = A.length(), M = B.length(); cout << numberofways(A, B, N, M) << endl; return 0; } |
JAVA
// Java Program for Number of ways to insert a // character to increase LCS by one import java.util.*; class GFG { static final int MAX = 256 ; // Return the Number of ways to insert a // character to increase the Longest // Common Subsequence by one static int numberofways(String A, String B, int N, int M) { Vector<Integer>[] pos = new Vector[MAX]; // Insert all positions of all characters // in string B. for ( int i = 0 ; i < MAX; i++) pos[i] = new Vector<>(); for ( int i = 0 ; i < M; i++) pos[B.charAt(i)].add(i + 1 ); // Longest Common Subsequence int [][] dpl = new int [N + 2 ][M + 2 ]; for ( int i = 1 ; i <= N; i++) { for ( int j = 1 ; j <= M; j++) { if (A.charAt(i - 1 ) == B.charAt(j - 1 )) dpl[i][j] = dpl[i - 1 ][j - 1 ] + 1 ; else dpl[i][j] = Math.max(dpl[i - 1 ][j], dpl[i][j - 1 ]); } } int LCS = dpl[N][M]; // Longest Common Subsequence from reverse int [][] dpr = new int [N + 2 ][M + 2 ]; for ( int i = N; i >= 1 ; i--) { for ( int j = M; j >= 1 ; j--) { if (A.charAt(i - 1 ) == B.charAt(j - 1 )) dpr[i][j] = dpr[i + 1 ][j + 1 ] + 1 ; else dpr[i][j] = Math.max(dpr[i + 1 ][j], dpr[i][j + 1 ]); } } // inserting character between position // i and i+1 int ans = 0 ; for ( int i = 0 ; i <= N; i++) { for ( int j = 0 ; j < MAX; j++) { for ( int x : pos[j]) { if (dpl[i][x - 1 ] + dpr[i + 1 ][x + 1 ] == LCS) { ans++; break ; } } } } return ans; } // Driver Code public static void main(String[] args) { String A = "aa" , B = "baaa" ; int N = A.length(), M = B.length(); System.out.println(numberofways(A, B, N, M)); } } // This code is contributed by // sanjeev2552 |
Python3
# Python Program to Number of ways to insert a # character to increase LCS by one MAX = 256 def numberofways(A, B, N, M): pos = [[] for _ in range ( MAX )] # Insert all positions of all characters # in string B for i in range (M): pos[ ord (B[i])].append(i + 1 ) # Longest Common Subsequence dpl = [[ 0 ] * (M + 2 ) for _ in range (N + 2 )] for i in range ( 1 , N + 1 ): for j in range ( 1 , M + 1 ): if A[i - 1 ] = = B[j - 1 ]: dpl[i][j] = dpl[i - 1 ][j - 1 ] + 1 else : dpl[i][j] = max (dpl[i - 1 ][j], dpl[i][j - 1 ]) LCS = dpl[N][M] # Longest Common Subsequence from reverse dpr = [[ 0 ] * (M + 2 ) for _ in range (N + 2 )] for i in range (N, 0 , - 1 ): for j in range (M, 0 , - 1 ): if A[i - 1 ] = = B[j - 1 ]: dpr[i][j] = dpr[i + 1 ][j + 1 ] + 1 else : dpr[i][j] = max (dpr[i + 1 ][j], dpr[i][j + 1 ]) # inserting character between position # i and i+1 ans = 0 for i in range (N + 1 ): for j in range ( MAX ): for x in pos[j]: if dpl[i][x - 1 ] + dpr[i + 1 ][x + 1 ] = = LCS: ans + = 1 break return ans # Driver Code if __name__ = = "__main__" : A = "aa" B = "baaa" N = len (A) M = len (B) print (numberofways(A, B, N, M)) # This code is contributed by vibhu4agarwal |
C#
// C# Program for Number of ways to insert a // character to increase LCS by one using System; using System.Collections.Generic; class GFG { static readonly int MAX = 256; // Return the Number of ways to insert a // character to increase the longest // Common Subsequence by one static int numberofways(String A, String B, int N, int M) { List< int >[] pos = new List< int >[MAX]; // Insert all positions of all characters // in string B. for ( int i = 0; i < MAX; i++) pos[i] = new List< int >(); for ( int i = 0; i < M; i++) pos[B[i]].Add(i + 1); // longest Common Subsequence int [,] dpl = new int [N + 2, M + 2]; for ( int i = 1; i <= N; i++) { for ( int j = 1; j <= M; j++) { if (A[i - 1] == B[j - 1]) dpl[i, j] = dpl[i - 1, j - 1] + 1; else dpl[i, j] = Math.Max(dpl[i - 1, j], dpl[i, j - 1]); } } int LCS = dpl[N, M]; // longest Common Subsequence from reverse int [,] dpr = new int [N + 2, M + 2]; for ( int i = N; i >= 1; i--) { for ( int j = M; j >= 1; j--) { if (A[i - 1] == B[j - 1]) dpr[i, j] = dpr[i + 1, j + 1] + 1; else dpr[i, j] = Math.Max(dpr[i + 1, j], dpr[i, j + 1]); } } // inserting character between position // i and i+1 int ans = 0; for ( int i = 0; i <= N; i++) { for ( int j = 0; j < MAX; j++) { foreach ( int x in pos[j]) { if (dpl[i, x - 1] + dpr[i + 1, x + 1] == LCS) { ans++; break ; } } } } return ans; } // Driver Code public static void Main(String[] args) { String A = "aa" , B = "baaa" ; int N = A.Length, M = B.Length; Console.WriteLine(numberofways(A, B, N, M)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript Program for Number of ways to insert a // character to increase LCS by one let MAX = 256; // Return the Number of ways to insert a // character to increase the Longest // Common Subsequence by one function numberofways(A,B,N,M) { let pos = new Array(MAX); // Insert all positions of all characters // in string B. for (let i = 0; i < MAX; i++) pos[i] =[]; for (let i = 0; i < M; i++) pos[B[i].charCodeAt(0)].push(i + 1); // Longest Common Subsequence let dpl = new Array(N + 2); for (let i=0;i<N+2;i++) { dpl[i]= new Array(M+2); for (let j=0;j<M+2;j++) dpl[i][j]=0; } for (let i = 1; i <= N; i++) { for (let j = 1; j <= M; j++) { if (A[i - 1] == B[j - 1]) dpl[i][j] = dpl[i - 1][j - 1] + 1; else dpl[i][j] = Math.max(dpl[i - 1][j], dpl[i][j - 1]); } } let LCS = dpl[N][M]; // Longest Common Subsequence from reverse let dpr = new Array(N + 2); for (let i=0;i<N+2;i++) { dpr[i]= new Array(M+2); for (let j=0;j<M+2;j++) dpr[i][j]=0; } for (let i = N; i >= 1; i--) { for (let j = M; j >= 1; j--) { if (A[i - 1] == B[j - 1]) dpr[i][j] = dpr[i + 1][j + 1] + 1; else dpr[i][j] = Math.max(dpr[i + 1][j], dpr[i][j + 1]); } } // inserting character between position // i and i+1 let ans = 0; for (let i = 0; i <= N; i++) { for (let j = 0; j < MAX; j++) { for (let x=0;x< pos[j].length;x++) { if (dpl[i][pos[j][x] - 1] + dpr[i + 1][pos[j][x] + 1] == LCS) { ans++; break ; } } } } return ans; } // Driver Code let A = "aa" , B = "baaa" ; let N = A.length, M = B.length; document.write(numberofways(A, B, N, M)); // This code is contributed by rag2127 </script> |
输出：
4
时间复杂性： O（N×M）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
