题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因(初次提交分数) |
---|---|---|---|---|---|
Subsequences Of Substrings | ★☆☆☆☆ | 答案正确 | 100 | 2015-2-22 21:08:21 | 没有用lld(10) |
(AC 458)
给定字符串s1,s2,要求s1首尾去除若干连续位后,s2仍然是s1的子串(子串的定义是s1移除若干位后为s2,如ac是abc的子串)。
xbaax baa
容易得到方案数为2*2=4种
xbaaxbaax baa
容易得到方案数为对于第一个baa,方案数为2*6种,第二个baa,除去之前算过的,共4*2种,合起来共20种。
xbaaa baa
容易得到方案数为2*2=4种(按照最前的匹配运算即可,同栗子1)
(s1.size()-j)*(i-last)//last为上一个i
统计求和即可[1],详见代码。
506.cpp代码已折叠
展开折叠内容
|
---|
#include<cstdio> #include<string> #include<iostream> #include<algorithm> using namespace std; #define si(n) scanf("%d",&n) #define ci const int & #define lld unsigned long long #define dsi(n) int n;si(n) #define f(i,n) for(int i=1;i<=n;++i) #define fi(i,p,n) for(int i=p;i<=n;++i) #define fd(i,n) for(int i=n;i!=0;--i) #define fdi(i,p,n) for(int i=n;i>=p;--i) int main() { string s1,s2; cin>>s1>>s2; lld last=-1,ans=0; fi(i,0,s1.size()-1) { if(s1[i]==s2[0]) { int p=0; fi(j,i,s1.size()-1) if(s1[j]==s2[p]) if(++p==s2.size()) { ans+=(lld)(s1.size()-j)*(i-last); last=i; break; } } } cout<<ans; return 0; } |