最长上升子串
1.给一个数组,求最长上升子串
思路:用dp来解,用dp[i]表示以a[i]结尾的最长上升子串的长度,那么它只用跟前一个比较,如果不能接在前一个后面那么就要重新开,即将dp[i]赋为1。因为不能跳,所以不能接就得断掉重开,由此实际上可以不用dp,我们直接遍历字符串,同时用sum来累计长度,用mx来记录最大值,断掉了就重来。
#include<bits/stdc++.h>
using namespace std;
int a[100];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
int mx=1,sum=1;
int c=a[1];
for(int i=2;i<=n;i++)
{
if(a[i]>c) sum++;
else
{
mx=max(mx,sum);
sum=1;
}
c=a[i];
}
mx=max(sum,mx);
cout<<mx;
}
2.求删掉一个字符后的最长上升子串
思路:这个与上面不同,上面是从前往后访问,断了就是断了,相当于就是统计连续字符个数,但是这里就要考虑删哪个字符,没办法只能暴力,将每个字符被删后的结果都算出来,所以最暴力的做法就是将每个字符去掉然后求一下最长上升字串,但是显而易见,太麻烦了,而且时间复杂度高,所以我们引入预处理来优化。我们将以每个字符开头和结尾的子串的最长上升字串长度求出来。当去掉一个字符后,只用看看前后能不能接起来,如果可以就用ans和q[i-1]+h[i+1]取最大值,否则就是ans,q[i-1],h[i+1]取最大值。
#include<bits/stdc++.h>
using namespace std;
int a[100010];
int t[100010],w[100010];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
w[1]=1;
int c=a[1];
for(int i=2;i<=n;i++)
{
if(a[i]>c) w[i]=w[i-1]+1;
else w[i]=1;
c=a[i];
}
t[n]=1;
c=a[n];
for(int i=n-1;i>=1;i--)
{
if(a[i]<c) t[i]=t[i+1]+1;
else t[i]=1;
c=a[i];
}
int ans=max(t[2],w[n-1]);
for(int i=2;i<=n-1;i++)
{
if(a[i-1]<a[i+1]) ans=max(ans,w[i-1]+t[i+1]);
else ans=max(ans,max(w[i-1],t[i+1]));
}
printf("%d",ans);
}
最长公共子串
1.给定两个字符串,求最长公共子串(s<=10000) (O(n^2))
#include<bits/stdc++.h>
using namespace std;
int dp[10010][10010];
char a[10010],b[10010];
int main()
{
scanf("%s%s",a+1,b+1);
//dp[i][j]以a[]的i结尾,b[]的j结尾的公共子序列的长度
int mx=0;
//strlen(a)=0
int n=strlen(a+1);
int m=strlen(b+1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=0;
mx=max(mx,dp[i][j]);
}
}
cout<<mx;
}
2.给定n个由小写字母构成的字符串,求出它们的最长公共子串的长度。
思路:字符串哈希+二分,
(n<=5,s<=2000)
#include<bits/stdc++.h>
using namespace std;
char s[10][2010];
const int N=2010;
typedef unsigned long long ull;
const int P=133;
ull p[2010],h[10][2010];
int n;
int check(int x)
{
map<ull,int>mp;
for(int i=1;i<=n;i++)
{
int l=strlen(s[i]+1);
set<ull>se;
for(int j=1;j<=l;j++)
{
if(j+x-1<=l)
{
ull t=h[i][j+x-1]-h[i][j-1]*p[x];//j+x-1-j+1
se.insert(t);
}
}
for(auto t:se) mp[t]++;
}
for(auto it:mp)
{
if(it.second==n) return 1;
}
return 0;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
p[0]=1;
for(int i=1;i<=N;i++) p[i]=p[i-1]*P;
int mi=3000;
for(int i=1;i<=n;i++)
{
int l=strlen(s[i]+1);
mi=min(mi,l);
for(int j=1;j<=l;j++)
h[i][j]=h[i][j-1]*P+s[i][j];
}
int l=0,r=mi;
while(l<r)
{
int mid=(l+r+1)/2;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<l;
}
3.给定两个字符串,求这两个字符串的不包含数字的最长公共子串的长度。 (s<=10000)
思路:直接在上题的基础上改改即可,唯一要注意的就是两个字符串的数字要被赋成不同的字符,这样包含数字的一定不是公共子串。
#include<bits/stdc++.h>
using namespace std;
char s[10][10010];
const int N=10010;
typedef unsigned long long ull;
const int P=133;
ull p[10010],h[10][10010];
const int n=2;
int check(int x)
{
map<ull,int>mp;
for(int i=1;i<=n;i++)
{
int l=strlen(s[i]+1);
set<ull>se;
for(int j=1;j<=l;j++)
{
if(j+x-1<=l)
{
ull t=h[i][j+x-1]-h[i][j-1]*p[x];//j+x-1-j+1
se.insert(t);
}
}
for(auto t:se) mp[t]++;
}
for(auto it:mp)
{
if(it.second==n) return 1;
}
return 0;
}
int main()
{
for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
int l1=strlen(s[1]+1),l2=strlen(s[2]+1);
for(int j=1;j<=l1;j++)
if(isdigit(s[1][j]))
s[1][j]='$';
for(int j=1;j<=l2;j++)
if(isdigit(s[2][j]))
s[2][j]='#';
p[0]=1;
for(int i=1;i<=N;i++) p[i]=p[i-1]*P;
int mi=10010;
for(int i=1;i<=n;i++)
{
int l=strlen(s[i]+1);
mi=min(mi,l);
for(int j=1;j<=l;j++)
h[i][j]=h[i][j-1]*P+s[i][j];
}
int l=0,r=mi;
while(l<r)
{
int mid=(l+r+1)/2;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<l;
}
最长回文串
manachar算法
include[HTML_REMOVED]
using namespace std;
int manacher(string str)
{
if(!str.length()) return 0;
int l=(int)(str.length()2+1);
char s=new char[l];//记录回文子串
int p=new int[l];//记录每个位置最大回文半径
int r,c,index,mx;
r=c=-1;
index=mx=0;
for(int i=0;i[HTML_REMOVED]i?min(r - i, p[2 * c - i]):1;
while(i+p[i][HTML_REMOVED]-1)//扩展后要在字符串内
{
if(s[i+p[i]]==s[i-p[i]]) p[i]++;//在已知半径的基础上往外扩展
else break;
}
/不断更新最远右边界的意义是,只有在这个边界内的才能利用回文的性质
随着访问右移,一定要往后找,所以要不断更新。*/
if(i+p[i]>r) //最远右边界
{
r=i+p[i];
c=i;
}
mx=max(mx,p[i]);
}
delete[] s;
delete[] p;
return mx-1;
}
int main()
{
string str;
getline(cin,str);//用来录入空格
cout<<manacher(str)<<endl;
return 0;
}
最大连续子序列和(连续子序列也即子串)
1.普遍
2.有条件的连续子序列
最长上升子序列
dp
最长公共子序列
dp
最长回文子序列
最大子序列和
将所有的正数加起来