------------恢复内容开始------------
D No-Subsequence Substring
知识点：双指针，模拟
有两种求法，一种是直接求满足条件的子串，一种是求不满足条件的子串，然后用总的减去不满足的就是答案。
赛时做的是第二种，感觉这个题有教育意义，去看题解果然学到了很多（）（也有可能是我水平太菜了）
void solve()
{string t;cin >> s >> t;n = s.size();m = t.size();s = ' ' + s;t = '#' + t;vvi nex(n + 4, vi(26, n + 1));//建一个nex数组，表示第i位开始j字母的位置for (int i = n; i >= 1; i--)//从后往前维护{nex[i] = nex[i + 1];nex[i][s[i] - 'a'] = i;}int ans = n * (n + 1) / 2;//总的子序列数量int cnt = 0;for (int l = 1; l <= n; l++)//双指针，左端点{int now = l;bool ok = 1;for (int i = 1; i <= m; i++)//依次枚举字符串t的每一位，看看是否存在{now = nex[now][t[i] - 'a'];if (now == n + 1){ok = 0;break;}now++;//找到一个之后，要让now到下一位，因为now本来那一位已经占了一位了}if (ok){now--;//因为每个循环都会让now++，所以最后会多加一个，所以now--；cnt += n - now + 1;//从now开始，到n，都是包含t的子串}}cout << ans - cnt << endl;
}
这是看别人代码的第一种
void solve()
{string t;cin >> s >> t;n = s.size();m = t.size();s = ' ' + s;t = '#' + t;vvi nex(n + 4, vi(26, n + 1));for (int i = n; i >= 1; i--){nex[i] = nex[i + 1];nex[i][s[i] - 'a'] = i;}int ans = n * (n + 1) / 2;int cnt = 0;for (int l = 1; l <= n; l++){int now = l;bool ok = 1;for (int i = 1; i <= m; i++){now = nex[now][t[i] - 'a'];if (now == n + 1){ok = 0;break;}now++;}if (ok){now -= 2;//now-=2回到前两位，就是刚刚好这个子串中没有t的子序列cnt += now - l + 1;//累加贡献}else{cnt += n - l + 1;//如果中途没查完就break了，说明后面这些再也不可能有含t子序列的s子串了，所以累加}}cout << cnt << endl;
}
E You WILL Like Sigma Problem
------------恢复内容结束------------