题解 | #公共子串计算#动态规划
公共子串计算
http://www.nowcoder.com/practice/98dc82c094e043ccb7e0570e5342dd1b
#include <iostream>
#include <vector>
#include<cstring>
using namespace std;
int main()
{
string s1 , s2 ;
getline(cin , s1) ;
getline(cin , s2) ;
vector<vector<int>> dp(s2.size() , vector<int>(s1.size())) ;
int size1 = s1.size() ;
int size2 = s2.size() ;
int max = 0 ;
for(int i = 0 ; i < size2 ; i++)
{
if(s2[i] == s1[0])
{
dp[i][0] = 1 ;
max = 1 ;
}
}
for(int j = 0 ; j < size1 ; j++)
if(s1[j] == s2[0])
{
dp[0][j] = 1 ;
max = 1 ;
}
for(int i = 1 ; i < size2 ; i++)
for(int j = 1 ; j < size1 ; j++)
{
if(s1[j] == s2[i])
{
dp[i][j] = dp[i - 1][j - 1] + 1 ;
if(dp[i][j] > max)
max = dp[i][j] ;
}
}
cout << max << endl ;
return 0;
}
#include <vector>
#include<cstring>
using namespace std;
int main()
{
string s1 , s2 ;
getline(cin , s1) ;
getline(cin , s2) ;
vector<vector<int>> dp(s2.size() , vector<int>(s1.size())) ;
int size1 = s1.size() ;
int size2 = s2.size() ;
int max = 0 ;
for(int i = 0 ; i < size2 ; i++)
{
if(s2[i] == s1[0])
{
dp[i][0] = 1 ;
max = 1 ;
}
}
for(int j = 0 ; j < size1 ; j++)
if(s1[j] == s2[0])
{
dp[0][j] = 1 ;
max = 1 ;
}
for(int i = 1 ; i < size2 ; i++)
for(int j = 1 ; j < size1 ; j++)
{
if(s1[j] == s2[i])
{
dp[i][j] = dp[i - 1][j - 1] + 1 ;
if(dp[i][j] > max)
max = dp[i][j] ;
}
}
cout << max << endl ;
return 0;
}