Codeforces 164B 是个字符串问题(codeforces把这类问题归为two pointers),给了2个字符串a,b都可以任意移位,且b中无相等元素,满足条件“是a的子串==是b的子序列”的最大的串 #includecstdio#
Codeforces 164B
是个字符串问题(codeforces把这类问题归为two pointers),给了2个字符串a,b都可以任意移位,且b中无相等元素,满足条件“是a的子串==是b的子序列”的最大的串
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int p[1000010],a[1000010],n,m,ans;
deque<int>q;
bool in(int x,int L,int R){
if(L<=R)return L<=x&&x<=R;
else return x<=R||L<=x;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i)scanf("%d",&a[i]);
memset(p,-1,sizeof p);
for(int i=0,x;i<m;++i){
scanf("%d",&x);
p[x]=i; // 利用串里无相同元素
}
for(int i=0;i<n+n;++i){
if(p[a[i%n]]==-1){
q.clear();
continue;
}
while(!q.empty()&&in(p[a[i%n]],q.front(),q.back())) //in函数判断p[a[i%n]]必须在选出的b序列的外面,否则的话队首元素出队
q.pop_front();
q.push_back(p[a[i%n]]);
ans=max(ans,(int)q.size());
if(ans>=min(m,n))
break;
}
printf("%d\n",ans);
return 0;
}
Codeforces 163A
Then:
f[i, j] = f[i, j + 1];
if (s[i] == t[j])
add(f[i, j], f[i + 1, j + 1] + 1)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define mod 1000000007
int dp[5010][5010];
int main(){
int i,j;
char s1[5010],s2[5010];
scanf("%s%s",s1,s2);
int len1=strlen(s1),len2=strlen(s2);
for(i=len1-1;i>=0;i--)
for(j=len2-1;j>=0;j--){
if(s1[i]==s2[j])
dp[i][j]=(dp[i][j+1]+1+dp[i+1][j+1])%mod;
else
dp[i][j]=(dp[i][j+1])%mod;
}
int sum=0;
for(i=len1-1;i>=0;i--)
sum=(sum+dp[i][0])%mod;
printf("%d\n",sum);
}
【感谢龙石为本站提供信息共享平台 http://www.longshidata.com/pages/exchange.html】