子序列

原题题面

题目背景

今天高川学习了子序列的概念，子序列就是在原来序列中（按顺序）找出一部分组成的序列，取出的子序列在原序列中可以不连续。

题目描述

例如，字符串 abccd 中， acd 是一个子序列，而 dc 则不是。

现在高川拿到了一个很长的字符串，他在研究里面子序列的种类问题。例如，对于字符串 abccd 来说，总共有两种子序列内容为 acd。（原串中第一，第三，第五个位置可以组成一个子序列 acd，并且第一，第四，第五个位置也可以组成一个子序列 acd，所以有两种）

高川姓高，拼音是 gao，他想知道在一个字符串中有多少个不同的子序列，其内容为 gao。

注意：对于两个内容均为 gao 的子序列来说，只要 gao 的这三个字母中的任何一个字母在原字符串中的位置不同，则认为这两个子序列是不同的子序列。

输入描述

第一行输入一个 n，代表字符串的长度。

接下来给出一个字符串，字符串仅由小写字母组成。

输出描述

输出一行一个整数表示答案。

输出时每行末尾的多余空格，不影响答案正确性

样例输入

5
ggaoo

样例输出

4

提示

对于 20% 的数据范围，满足 1≤n≤100

对于 60% 的数据范围，满足 1≤n≤1000

对于 100% 的数据范围，满足1≤n≤1000000

解析

此题有两种思路，一种思路比较复杂，由暴力枚举一步步优化而来；而这里介绍的是笔者发现的另一种方法。

从“1”开始

一切归纳的思想都由最简单的境况开始。我们首先来看以下这个简化版的问题：

给你一个字符序列，求这个序列中有几个字符‘g’。

很显然，这个题目用一个for循环就能实现（事实上本人觉得题目给的n还是不用为妙，万一数据出错了呢( ）。

string s;
cin>>s;
long long cnt=0;//计数器别忘了用longlong与归零
for(int i=0;i
    <s.length();i++){ if(s[i]="='g'){" cnt++;="" }="" }<="" ode=""></s.length();i++){>

<p> </p> <p> </p> <h2>向“2”进发</h2> <p> </p> <p> </p> <p>让我们再升级一下问题：</p> <p> </p> <p> </p>

给你一个字符序列，求这个序列中有几个子序列为‘ga’。

思索一番

让我们深入思考一下。在上面的代码中，您已经能统计出有几个‘g’的个数了。然而，想要组成‘ga’的子序列，就必须找到对于每一个‘g’来说后面有几个‘a’。显而易见，这种方式的复杂度到达了O(n²)，是肯定要超时的。

思考一下，在什么情况下复杂度能到达O(n)？比如在上一块内容中，我们是枚举每一个‘g’，对‘g’来说复杂度是O(n)。

所以，想要在寻找‘a’的时候将复杂度将为O(n)，何尝不妨以‘a’为枚举对象，同时保留对‘g’的统计，然后进行操作呢？这样，把两样东西放在同一个for循环中，复杂度将保留至O(n)。

如何实现

既然我们能在任意时刻获得该字符前‘g’的个数，那么在‘a’之前当然可以获得之前有几个‘g’了。‘ga’的个数就是在遇到‘a’的时候将其前面所有的‘g’的个数累加起来即可。

#include
     <bits tdc++.h="">

using namespace std;
long n;
string s;
long long g,ga;
int main(){
	cin>>n>>s;
	for(int i=0;i
      <n;i++){ if(s[i]="='a')ga+=g;" else="" }="" cout<<ga;="" return="" 0;="" }<="" ode=""></n;i++){>
     </bits>

<p> </p> <p> </p> <h1>奔向终点</h1> <p> </p> <p> </p> <p>有了如上的称述，进行举一反三，相信很快就能归纳出当3个字符‘gao’的子序列的代码来。</p> <p> </p> <p> </p> <pre class="wp-block-code">#include <bits tdc++.h="">

using namespace std; long n; string s; long long g,ga,gao; int main(){ cin>>n>>s; for(int i=0;i <n;i++){ if(s[i]=”=’o’)gao+=ga;” else=”” }=”” cout«gao;=”” return=”” 0;=”” }<=”” ode=””></n;i++){> </bits></code></pre> <p> </p> <p> </p> <p>同样，当遇到‘o’的时候，只需要累加其前面出现过的‘ga’的次数即可。</p> <p> </p> <p> </p> <h1>更进一步</h1> <p> </p> <p> </p> <p>有了如上铺垫，我们还可以尝试将题目改为这样：</p> <p> </p> <p> </p> <blockquote class="wp-block-quote"> <p>给你两个字符串s1和s2，求s2当中有多少个子序列为s1。</p> <p>保证s1.length()<=s2.length()。</p> </blockquote> <p> </p> <p> </p> <p>那么，我们可以使用一个数组来保存目标子序列s1，在对s2进行搜索时同时遍历s1，并将计数的结果也保存在一个数组中。</p> <p> </p> <p> </p> <p>这样，时间复杂度即为O(n²)。</p> <p> </p> </code></code>