学校前一段时间的作业，个人觉得题目挺好的，故把这些题目放到CSDN上。

目录

最长回文子串

最长公共子串

判断两个字符串是否匹配

最长回文子串

【问题描述】给定一个字符串s，找出s里第一次出现的最长的回文子串。

【样例输入1】babad
【样例输出1】bab

【样例输入2】cbbd
【样例输出2】bb

dp[i][j]代表从i到j这个子串是否为回文子串，为了方便起见，我们规定单个字符为回文子串。

首先我们先排查两个字符的回文子串，也就是两个字符相等。

for(int i=0;i 
flag的作用是找出第一个出现的两个字符的回文子串。
 
下面是正式过程，我们的核心思想是这样的：如果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"<