学校前一段时间的作业，个人觉得题目挺好的，故把这些题目放到CSDN上。
目录
最长回文子串
最长公共子串
判断两个字符串是否匹配
最长回文子串
【问题描述】给定一个字符串s，找出s里第一次出现的最长的回文子串。
【样例输入1】babad
【样例输出1】bab
【样例输入2】cbbd
【样例输出2】bb
dp[i][j]代表从i到j这个子串是否为回文子串，为了方便起见，我们规定单个字符为回文子串。
首先我们先排查两个字符的回文子串，也就是两个字符相等。
for(int i=0;iflag的作用是找出第一个出现的两个字符的回文子串。
下面是正式过程，我们的核心思想是这样的：如果dp[i+1][j-1]为真同时s[i]和s[j]相等，我们就可以确定dp[i][j]为真。
我们从回文子串为3开始搜索，寻找最长的子串
for(int len=3;len<=n;len++)
{
for(int i=0;i<=n-len;i++)
{
int j=i+len-1;
if(dp[i+1][j-1]&&s[i]==s[j])
{
dp[i][j]=1;
if(len>max)
{
start=i;
max=len;
}
}
}
}完整代码附上
#include
using namespace std;
int main()
{
string s;
cin>>s;
int n=s.size();
bool dp[100][100]={0};
int start=0,max=0,flag=1;
for(int i=0;imax)
{
start=i;
max=len;
}
}
}
}
for(int i=start;i<=start+max-1;i++)
cout< 【问题描述】
给定两个字符串，求出它们两个最长的相同子字符串的长度。
最长公共子串(Longest Common Substring)是一个非常经典的面试题目，在实际的程序中也有很高的实用价值。同学们不应该单单只是写出该问题的基本解决代码而已，关键还是享受把算法一步步的优化，让时间和空间复杂度一步步的减少的惊喜。
【输入形式】
两个字符串
【输出形式】
最长的公共子串，若没有则输出“no”
【样例输入】
acbcbcef
abcbced
【样例输出】
bcbce
同样首先我们给出dp[i][j]的定义：dp[i][j]代表s1的前i个字符和s2的前j个字符最长子串的长度
很容易得到 如果s1的第i个字符与s2的第j个字符相等
显然有 dp[i][j]=dp[i-1][j-1]+1,不过需要注意的是当i或j其中有一个为0的时候需要特判一下
代码如下
#include
using namespace std;
int dp[100][100]={0};
int main()
{
string s1,s2;
cin>>s1;
cin>>s2;
int m=s1.size();
int n=s2.size();
int max=0,end=0;
for(int i=0;imax)
{
max=dp[i][j];
end=i;
}
}
}
for(int i=end-max+1;i<=end;i++)
cout< 【问题描述】判断两个字符串是否匹配，其中一个字符串中包括通配符*或？（串）。*代表0个或多个字符，？代表一个字符
【输入形式】分两行入两个字符串，以#结束，其中一个字符串中包括通配符*或？（串），另一个为不包含*和？的确定字符串
【输出形式】判断两个字符串是否匹配，若匹配，输出yes，不匹配输出no
【样例输入】da?a*tu*e#
datastructure#
【样例输出】
yes
【样例说明】 第一个字符串中包含通配符，第二个字符串为确定字符串。字符串中可能有空格，字母均为小写字母。
【评分标准】 请尽量使用效率高的算法，如结合KMP算法的思想。提示：？可看做对任一字符的匹配，*可看做对给出的有效字符（串）的匹配。
这道题首先要注意字符串中有空格，不能直接用cin读入,本人血泪教训，一定要用getline 来读入！！！
dp[m][n]代表s1的前m个字符是否和s2的前n个字符匹配，我们将dp[0][0]的初值赋为1
首先先来一个特判考虑*出现在开头怎么办
for(int i=1;i<=m;i++)
{
if(s1[i-1]=='*'&&dp[i-1][0])
dp[i][0]=1;
}如果s1[i-1]=s2[j-1]或者s1[i-1]='?'
那么此时二者就是匹配的，转移方程就是dp[i][j]=dp[i-1][j-1]
如果s1对应的字符是一个通配符*
我们就要比较前面的子串，由于*可以代表一个或多个字符，
此时的dp[i][j]=dp[i-1][j]||dp[i][j-1],
#include
using namespace std;
int main()
{
string s1,s2;
getline(cin,s1);
getline(cin,s2);
int m=s1.size();
int n=s2.size();
bool dp[100][100];
dp[0][0]=1;
for(int i=1;i<=m;i++)
{
if(s1[i-1]=='*'&&dp[i-1][0])
dp[i][0]=1;
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(s1[i-1]==s2[j-1]||s1[i-1]=='?')
dp[i][j]=dp[i-1][j-1];
else if(s1[i-1]=='*')
{
dp[i][j]=dp[i-1][j]||dp[i][j-1];
}
}
}
if(dp[m][n])
cout<<"yes"< 欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）