題意：在一個(gè)母串X中找出字串Z出現(xiàn)的最大次數(shù)。
解法：很明顯的DP；狀態(tài)表示：用a[i][j]表示字串的前i個(gè)在母串的前j個(gè)中出現(xiàn)得最大次數(shù)；轉(zhuǎn)移方程：始終有a[i][j] = a[i][j-1]，因?yàn)樽执癷個(gè)在母串前j-1個(gè)中出現(xiàn)的次數(shù)顯然也會(huì)在母串前j個(gè)出現(xiàn)，當(dāng)x[j]==z[i]時(shí)，還要加上字串前i-1個(gè)在母串前j-1個(gè)出現(xiàn)的次數(shù)。可以轉(zhuǎn)化為一維的，具體見代碼：
#include<iostream>
#include<algorithm>
using namespace std;
#define Base 1000000000
#define Cap 30
typedef long long hugeint;
struct bignum
{
int Len;
int Data[Cap];
bignum() : Len(0){}
bignum(const bignum &V) : Len(V.Len)
{
memcpy(Data,V.Data,Len * sizeof*Data);
}
bignum(int V) : Len(0)
{
for(;V > 0;V /= Base)
Data[Len++] = V % Base;
}
bignum &operator = (const bignum &V)
{
Len = V.Len;
memcpy(Data,V.Data,Len * sizeof*Data);
return *this;
}
int &operator[](int Index)
{
return Data[Index];
}
int operator[](int Index) const
{
return Data[Index];
}
};
bignum operator+(const bignum &A, const bignum &B)
{
bignum R;
int i;
int Carry = 0;
for(i = 0; i < A.Len || i < B.Len || Carry > 0; i++)
{
if(i < A.Len)
Carry += A[i];
if(i < B.Len)
Carry += B[i];
R[i] = Carry % Base;
Carry /= Base;
}
R.Len = i;
return R;
}
ostream& operator<<(ostream &Out, const bignum &V)
{
int i;
Out << (V.Len == 0 ? 0 : V[V.Len - 1]);
for(i = V.Len - 2; i >= 0; i--)
for(int J = Base / 10; J > 0; J /= 10)
Out << V[i] / J % 10;
return Out;
}
#define M 105
#define N 10005
bignum d[M];
char s1[N], s2[M];
int main()
{
int t, l1, l2;
scanf("%d", &t);
while(t--)
{
scanf("%s %s", &s1, &s2);
l1 = strlen(s1), l2 = strlen(s2);
for(int i = 1; i <= l2; i++) d[i] = bignum(0);
d[0] = bignum(1);
for(int i = 1; i <= l1; i++)
for(int j = l2; j >= max(l2 - l1 + i, 1); j--)
{
if(s1[i - 1] == s2[j - 1])
{
d[j] = d[j] + d[j - 1];
}
}
cout <<d[l2]<<endl;
}
return 0;
}