Sgu/506

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
Subsequences Of Substrings	★☆☆☆☆	答案正确	100	2015-2-22 21:08:21	没有用lld（10）

（AC 458）

题意

给定字符串s1,s2，要求s1首尾去除若干连续位后，s2仍然是s1的子串（子串的定义是s1移除若干位后为s2，如ac是abc的子串）。

题解

• 栗子1：

显示/移除行号

xbaax
baa

容易得到方案数为2*2=4种

• 栗子2：

显示/移除行号

xbaaxbaax
baa

容易得到方案数为对于第一个baa，方案数为2*6种，第二个baa，除去之前算过的，共4*2种，合起来共20种。

• 栗子3：

显示/移除行号

xbaaa
baa

容易得到方案数为2*2=4种（按照最前的匹配运算即可，同栗子1）

• 类比得到匹配一段字符串从索引i至索引j，其方案数为：

显示/移除行号

   (s1.size()-j)*(i-last)//last为上一个i

统计求和即可，详见代码。

代码

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; }