子串要求連續
子序列不要求連續
之前的做法是dp求子序列
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
string s1,s2;
int dp[1010][1010];//s1串前i個字元和s2串前j個字元的最長公共子串
int main ()
{
while (cin>>s1>>s2)
{
memset(dp,0,sizeof(dp));
for (int i=1; i<=s1.length(); i++)//i指向串s1
{
for (int j=1; j<=s2.length(); j++)//j指向串s2
{
if (s1[i-1] == s2[j-1])//如果目前字元相同,i,j均向右移一位,目前最大長度就為前一個情況加1
dp[i][j] = dp[i-1][j-1]+1;
else//否則,要麼i向右移一位,要麼j向右移一位,長度不變
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
cout<<dp[s1.length()][s2.length()]<<endl;
}
return 0;
}
子串就是如果不比對就清空為0
維護最大值即可
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[500][500];
char str1[500],str2[500];
int main()
{
//freopen("cin.txt","r",stdin);
while(~scanf("%s%s",str1,str2))
{
// printf("%s %s\n",str1,str2);
memset(dp,0,sizeof(dp));
int len1=strlen(str1),len2=strlen(str2);
int maxlen=0;
for(int i=0;i<len1;i++)
for(int j=0;j<len2;j++)
{
if(str1[i]==str2[j])
{
dp[i+1][j+1]=dp[i][j]+1;
maxlen=maxlen>dp[i+1][j+1]?maxlen:dp[i+1][j+1];
}
else dp[i+1][j+1]=0;
}
printf("%d\n",maxlen);
}
return 0;
}