查看Sgu/506的源代码 ←Sgu/506

[[分类:组合数学]]
==摘要==
{{信息题|Subsequences Of Substrings|http://acm.sgu.ru/problem.php?contest{{=}}0&problem{{=}}506|1|100|没有用lld|10|time=2015-2-22 21:08:21}}
（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种（按照最前的匹配运算即可）
 
类比得到匹配一段字符串从索引i至索引j，其方案数为：
    (s1.size()-j)*(i-last)//last为上一个i
统计求和即可<ref>http://vawait.com/sgu-506/</ref>，详见代码。

==代码==
{{折叠|506.cpp代码已折叠
|<pre>
#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;
}
</pre>
|sgu506}}
==参考资料和拓展阅读==
<references/>