http://acm.sgu.ru/problem.php?contest=0&problem=506Summer Training #2 DIV1，被完虐！
題意讀了兩個(gè)多小時(shí)！！！！
題意不說了，
第一種做法：
#define maxn 100010
#define maxm 120
using namespace std;
char a[maxn],b[maxm];
int cnt[27],p[27][maxn],now[maxm];
int main()
{
scanf("%s",a);
scanf("%s",b);
int n=strlen(a);
int m=strlen(b);
clr(cnt);
for (int i=0;i<n;i++)
{
int tmp=a[i]-'a';
p[tmp][cnt[tmp]++]=i;
}
long long ans=0;
clr(now);
for (int i=0;i<n;i++)
{
int last=i-1;
int begin;
bool flag=1;
for (int j=0;j<m;j++)
{
int tmp=b[j]-'a';
while (now[j]<cnt[tmp] && p[tmp][now[j]]<=last)
now[j]++;
if (now[j]==cnt[tmp])
{
flag=0;
break;
}
last=p[tmp][now[j]];
if (j==0)
begin=last;
}
if (!flag)
break;
ans+=(n-last)*(begin-i+1);
i=begin;
}
printf("%I64d\n",ans);
return 0;
}
很詭異的是后面這個(gè)DP做法，第一次提交的時(shí)候居然：
搞不清楚Global Error是什么錯(cuò)誤，重新提交了一下代碼，AC了：
#define maxn 100010
#define maxm 120
using namespace std;
char a[maxn],b[maxm];
int dp[maxn][maxm];
int main()
{
scanf("%s%s",a,b);
int n=strlen(a);
int m=strlen(b);
clr(dp);
for (int i=0;i<=n;i++)
dp[i][0]=1;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
if (a[i-1]==b[j-1])
dp[i][j]+=dp[i-1][j-1];
else
dp[i][j-1]+=dp[i-1][j-1];
}
}
long long ans=0;
for (int i=m;i<=n;i++)
ans+=dp[i][m]*(n-i+1);
printf("%I64d\n",ans);
return 0;
}