大意不再赘述。
思路:状态方程是最常见的,但我没想出来,在中途我又去学了C++ bign高精度,有利有弊,谨慎使用,时间复杂度很高的,因为s数组开到1010CE了许多次,400就会TLE。
状态转移方程:
d[i][j] = d[i][j-1] (y[i] != x[j])
d[i][j] = d[i][j] + d[i-1][j-1] (y[i] == x[j])
这里表示的意义是d[i][j]表示子串前i 个组成的子串,在前j 个母串中出现的次数,为什么要这么表示呢?
当y[i] != x[j]时,d[i][j] >= d[i][j-1]
当y[i] == x[j]时,可以由当前的状态加上前i-1个子串在前j-1个母串中出现的次数。
具体实现是,子串循环在外面,母串在里面。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <algorithm> using namespace std; const int MAXN = 110; //数组越大,时间复杂度越高啊,谨慎使用。 char X[10010], Y[110]; struct bign { int len, s[MAXN]; bign() { memset(s, 0, sizeof(s)); len = 1; } bign operator = (const char *num) { len = strlen(num); for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0'; return *this; } bign operator = (const int num) { char s[MAXN]; sprintf(s, "%d", num); *this = s; return *this; } bign (int num) { *this = num;} bign (char *num) { *this = num;} bign operator + (const bign &b) { bign c; c.len = 0; for(int i = 0, g = 0; g || i < max(len, b.len); i++) { int x = g; if(i < len) x += s[i]; if(i < b.len) x += b.s[i]; c.s[c.len++] = x % 10; g = x / 10; } return c; } bign operator - (const bign &b) { bign c; c.len = 0; for(int i = 0; i < max(len, b.len); i++) { c.s[i] += s[i]-b.s[i]; if(c.s[i] < 0) { c.s[i] += 10; c.s[i+1]--; } } while(c.s[len-1] == 0 && len > 1) len--; c.len = len; return c; } bign operator += (const bign &b) { *this = *this + b; return *this; } string str() const { string res = ""; for(int i = 0; i < len; i++) res = char(s[i] + '0') + res; if(res == "") res = "0"; return res; } }d[110][10010]; istream& operator >> (istream& in, bign &x) { string s; in >> s; x = s.c_str(); return in; } ostream& operator << (ostream& out, bign &x) { out << x.str(); return out; } void solve() { scanf("%s%s", X+1, Y+1); int lenX = strlen(X+1), lenY = strlen(Y+1); for(int i = 0; i <= lenX; i++) d[0][i] = 1; for(int i = 1; i <= lenY; i++) { for(int j = i; j <= lenX; j++) { d[i][j] = d[i][j-1]; if(Y[i] == X[j]) d[i][j] += d[i-1][j-1]; } } cout<<d[lenY][lenX]<<endl; } int main() { int T; scanf("%d", &T); while(T--) { solve(); } return 0; }