摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 失误原因(初次提交分数)
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

统计求和即可[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;
}

参考资料和拓展阅读

  1. http://vawait.com/sgu-506/

著作权声明[编辑]

关于[编辑]