加密
【问题描述】
有一种不讲道理的加密方法是： 在字符串的任意位置随机插入字符。 相应的，不讲道理的解密方法就是从字符串中恰好删去随机插入的那些字符。给定原文s和加密后的字符串t，求t有多少子串可以通过解密得到原文s。
【输入格式】
输入第一行包含一个字符串t，第二行包含一个字符串s。
【输出格式】
输出一行，包含一个整数，代表可以通过解密得到原文的t的子串的数量。
【样例输入】
abcabcabc
cba
【样例输出】
9
【样例解释】
用[l,r]表示子串开头结尾的下标（从 0 开始编号） ，这 9 种方案是：[0,6],[0,7],[0,8],[1,6],[1,7],[1,8],[2,6],[2,7],[2,8]
【数据规模和约定】
对于30%的数据，|t| ≤1000。
对于100%的数据，1 ≤ |t| ≤ 300,000，1 ≤ |s| ≤ 200。
【题目分析】
给出字符串t，从t的子串中按顺序找出s中的每一个字符（不一定连续）。
举个例子来说
t：qqacbbaccbcsd
s：ab
发现s在t中出现了不止一次啊这尼玛怎么搞会有重复啊。
淡定。
定义last为上一次找到的s串中第一个元素出现的位置，初始值为0
扫描t串找到s的第一个元素在中出现的位置时，记录为i，从这个位置开始继续往后扫，直到把s串中的元素恰好全都找到时停止，位置记录为j，那也就是说从i到j这段的字符都必须有然后两边依次加字符，那利用[i,j]这段字符串的方案数就为(i)*(len1-j+1)这是第一次扫描到s第一个元素时，如果不是第一次的话，我们就不能直接用i乘了，因为那会和前面已经计入答案的方案重复，这玩意手推一下就好。所以 方案数应该是(i-last)*(len1-j+1)，last为上一次s的第一个元素出现的位置，这也就解释了为什么初始为0。
再看一种情况，上面的例子中 出现了acbb，这种情况下只要计算第一个b就好了，因为计算第一个的时候第二个的所有情况都包含在内，而计算第二个却没办法把第一个包含（额...语文水平有限，太罗嗦），这就是为嘛扫一遍就能计算出正确答案。
#include <cstdio> #include <cstring> #include <iostream> using namespace std; int len1,len2; long long ans; char t[300010],s[205]; int main() { freopen("encrypt.in","r",stdin); freopen("encrypt.out","w",stdout); scanf("%s",t+1); scanf("%s",s+1); len1=strlen(t+1); len2=strlen(s+1); int last=0; for(int i=1;i<=len1;i++) { int cnt=1,j; if(t[i]==s[1]) { for(j=i;j<=len1;j++) { if(cnt==len2+1) break; if(t[j]==s[cnt]) cnt++; } if(cnt==len2+1) j--, ans+=(i-last)*(len1-j+1), last=i; } } cout<<ans; fclose(stdin);fclose(stdout); return 0; }