密码（substring）题解
【问题描述】
假发通过了不懈的努⼒，得到了将军家门锁的密码（⼀串⼩写英⽂字母）。但是假发被⼗四和猩猩他们盯上了，所以假发需要把密码传递出去。因为假发不想⼗四他们发现⼏松门前贴的⼩纸条就是将军家的密码，所以他加密了密码（新⼋：听起来有点诡异）。加密⽅法如下：随机地，在密码中任意位置插⼊随机长度的⼩写字符串。
不过，假发相信银桑和他那么多年⼩学同学，⼀定能猜中密码是什么的（新⼋：银桑什么时候成攮夷志⼠了）。可是，写完了⼩纸条之后，假发觉得有点长，就想截去头和尾各⼀段（可以为空），让剩下的中间那⼀段依然包含真～密码。想着想着，假发就想知道有多少种可⾏⽅案。结果在沉迷于稿纸之际，假发被投进了狱门岛（新⼋：……）。于是，就由你计算了。
【输⼊】
两⾏⾮空字符串，纯⼩写英⽂字母，第⼀⾏是加密后的密码，第⼆⾏是原密码。
第⼀⾏长度不超过300000，第⼆⾏不超过200。
【输出】
⼀⾏，有多少种⽅案。注意：不剪也是⼀种⽅案。
【输⼊输出样例】
abcabcabc
cba 9
【样例解释】
⽤(L,R)表⽰⼀种⽅案，其中L和R分别表⽰截去头和尾的长度。这9钟⽅案分别是(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)。
【数据说明】
30%的数据满⾜第⼀⾏长度不超过1000。
这⼀题如果是纯暴⼒做的话，只能拿到30分的好成绩（。然⽽，这题的标算也是暴⼒(!)，它是这样写的：
先记录密码第⼀位字母在第⼀个字符串中的位置。如果匹配成功，就把第⼀位字母的位置传递下去；
每扫⼀次，就加上最后⼀位字母的位置；
这就是正解的全部内容！
上代码
#include<bits/stdc++.h>
using namespace std;
char a[300005],b[300005];
int f[300005];
long long ans;
int main(){
gets(a+1);
gets(b+1);
int n=strlen(a+1),m=strlen(b+1);
for(int i=1;i<=n;i++)
{
字符串长度什么时候算0f[0]=i;
for(int j=m;j>=1;j--)
{
if(a[i]==b[j]) f[j]=f[j-1];
}
ans+=f[m];
}
cout<<ans;
return 0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。