Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define MEMSET_INF 127
- #define MEMSET_HALF_INF 63
- #define stream istringstream
- #define rep(i,n) for(__typeof(n) i=0; i<(n); i++)
- #define repl(i,n) for(__typeof(n) i=1; i<=(n); i++)
- #define FOR(i,a,b) for(__typeof(b) i=(a); i<=(b); i++)
- #define INF (1<<30)
- #define PI acos(-1.0)
- #define pb push_back
- #define ppb pop_back
- #define all(x) x.begin(),x.end()
- #define mem(x,y) memset(x,y,sizeof(x))
- #define memsp(x) mem(x,MEMSET_INF)
- #define memdp(x) mem(x,-1)
- #define memca(x) mem(x,0)
- #define eps 1e-9
- #define pii pair<int,int>
- #define pmp make_pair
- #define ft first
- #define sd second
- #define vi vector<int>
- #define vpii vector<pii>
- #define si set<int>
- #define msi map<string , int >
- #define mis map<int , string >
- typedef long long i64;
- typedef unsigned long long ui64;
- /** function **/
- #define SDi(x) sf("%d", &x)
- #define SDl(x) sf("%lld", &x)
- #define SDs(x) sf("%s", x)
- #define SD2(x,y) sf("%d%d", &x, &y)
- #define SD3(x,y,z) sf("%d%d%d", &x, &y, &z)
- #define pf printf
- #define print(x) pf("%d ", x)
- #define sf scanf
- #define READ(f) freopen(f, "r", stdin)
- #define WRITE(f) freopen(f, "w", stdout)
- const i64 INF64 = (i64)1E18;
- template<class T> inline T gcd(T a,T b) {
- if(a<0)return gcd(-a,b);
- if(b<0)return gcd(a,-b);
- return (b==0)?a:gcd(b,a%b);
- }
- template<class T> inline T lcm(T a,T b) {
- if(a<0)return lcm(-a,b);
- if(b<0)return lcm(a, -b);
- return a*(b/gcd(a,b));
- }
- template<class T> inline T sqr(T x) {
- return x*x;
- }
- template<class T> T power(T N,T P) {
- return (P==0)? 1: N*power(N,P-1);
- }
- template<class T> bool inside(T a,T b,T c) {
- return (b>=a && b<=c);
- }
- double _dist(double x1,double y1,double x2,double y2) {
- return sqrt(sqr(x1-x2)+sqr(y1-
- y2));
- }
- int distsq(int x1,int y1,int x2,int y2) {
- return sqr(x1-x2)+sqr(y1-y2);
- }
- i64 toInt64(string s) {
- i64 r=0;
- istringstream sin(s);
- sin>>r;
- return r;
- }
- double Log(i64 N, i64 B) {
- return (log10l(N)) / (log10l(B));
- }
- string itoa(long long a) {
- if(a==0) return "0";
- string ret;
- for(long long i=a; i>0; i=i/10)
- ret.push_back((i%10)+48);
- reverse(ret.begin(),ret.end());
- return ret;
- }
- vector< string > token( string a, string b ) {
- const char *q = a.c_str();
- while( count( b.begin(), b.end(), *q ) ) q++;
- vector< string > oot;
- while( *q ) {
- const char *e = q;
- while( *e && !count( b.begin(), b.end(), *e ) )
- e++;
- oot.push_back( string( q, e ) );
- q = e;
- while( count( b.begin(), b.end(), *q ) )
- q++;
- }
- return oot;
- }
- int isvowel(char s) {
- s=tolower(s);
- if(s=='a' or s=='e' or s=='i' or s=='o' or s=='u')
- return 1;
- return 0;
- }
- int isupper(char s) {
- if(s>='A' and s<='Z') return 1;
- return 0;
- }
- template<class T> struct Fraction {
- T a,b;
- Fraction(T a=0,T b=1);
- string
- toString();
- };//NOTES:Fraction
- template<class T> Fraction<T>::Fraction(T a,T b) {
- T d=gcd(a,b);
- a/=d;
- b/=d;
- if (b<0) a=-a, b=-b;
- this->a=a;
- this->b=b;
- }
- template<class T> string Fraction<T>::toString() {
- ostringstream
- sout;
- sout<<a<<"/"<<b;
- return sout.str();
- }
- template<class T> Fraction<T> operator+(Fraction<T> p,Fraction<T> q) {
- return
- Fraction<T>(p.a*q.b+q.a*p.b,p.b*q.b);
- }
- template<class T> Fraction<T> operator-(Fraction<T> p,Fraction<T> q) {
- return
- Fraction<T>(p.a*q.b-q.a*p.b,p.b*q.b);
- }
- template<class T> Fraction<T> operator*(Fraction<T> p,Fraction<T> q) {
- return
- Fraction<T>(p.a*q.a,p.b*q.b);
- }
- template<class T> Fraction<T> operator/(Fraction<T> p,Fraction<T> q) {
- return
- Fraction<T>(p.a*q.b,p.b*q.a);
- }
- /** BitMask **/
- int Set(int N, int pos) {
- return N = N | (1 << pos);
- }
- int Reset(int N,int pos) {
- return N = N & ~(1 << pos);
- }
- int Check(int N, int pos) {
- return (N & (1 << pos));
- }
- int toggle(int N, int pos) {
- if( Check(N, pos) )
- return N = Reset(N, pos);
- return N = Set(N, pos);
- }
- const i64 INFFF = 1e16;
- #define Max 10005
- #define Mx 105
- char X[Max], Z[Mx];
- int total, length, n;
- // i = sequence index, indx = subsequence index
- void solve(int indx, int i) {
- if(indx == length) {
- ++total;
- return;
- }
- if( i >= n - (length - 1 - indx) )
- return;
- if(X[i] == Z[indx])
- solve(indx + 1, i + 1);
- solve(indx, i + 1);
- }
- struct Bigint {
- // representations and structures
- string a; // to store the digits
- int sign; // sign = -1 for negative numbers, sign = 1 otherwise
- // constructors
- Bigint() {} // default constructor
- Bigint( string b ) {
- (*this) = b; // constructor for string
- }
- // some helpful methods
- int size() { // returns number of digits
- return a.size();
- }
- Bigint inverseSign() { // changes the sign
- sign *= -1;
- return (*this);
- }
- Bigint normalize( int newSign ) { // removes leading 0, fixes sign
- for( int i = a.size() - 1; i > 0 && a[i] == '0'; i-- )
- a.erase(a.begin() + i);
- sign = ( a.size() == 1 && a[0] == '0' ) ? 1 : newSign;
- return (*this);
- }
- // assignment operator
- void operator = ( string b ) { // assigns a string to Bigint
- a = b[0] == '-' ? b.substr(1) : b;
- reverse( a.begin(), a.end() );
- this->normalize( b[0] == '-' ? -1 : 1 );
- }
- // conditional operators
- bool operator < ( const Bigint &b ) const { // less than operator
- if( sign != b.sign ) return sign < b.sign;
- if( a.size() != b.a.size() )
- return sign == 1 ? a.size() < b.a.size() : a.size() > b.a.size();
- for( int i = a.size() - 1; i >= 0; i-- ) if( a[i] != b.a[i] )
- return sign == 1 ? a[i] < b.a[i] : a[i] > b.a[i];
- return false;
- }
- bool operator == ( const Bigint &b ) const { // operator for equality
- return a == b.a && sign == b.sign;
- }
- // mathematical operators
- Bigint operator + ( Bigint b ) { // addition operator overloading
- if( sign != b.sign ) return (*this) - b.inverseSign();
- Bigint c;
- for(int i = 0, carry = 0; i<a.size() || i<b.size() || carry; i++ ) {
- carry+=(i<a.size() ? a[i]-48 : 0)+(i<b.a.size() ? b.a[i]-48 : 0);
- c.a += (carry % 10 + 48);
- carry /= 10;
- }
- return c.normalize(sign);
- }
- Bigint operator - ( Bigint b ) { // subtraction operator overloading
- if( sign != b.sign ) return (*this) + b.inverseSign();
- int s = sign;
- sign = b.sign = 1;
- if( (*this) < b ) return ((b - (*this)).inverseSign()).normalize(-s);
- Bigint c;
- for( int i = 0, borrow = 0; i < a.size(); i++ ) {
- borrow = a[i] - borrow - (i < b.size() ? b.a[i] : 48);
- c.a += borrow >= 0 ? borrow + 48 : borrow + 58;
- borrow = borrow >= 0 ? 0 : 1;
- }
- return c.normalize(s);
- }
- Bigint operator * ( Bigint b ) { // multiplication operator overloading
- Bigint c("0");
- for( int i = 0, k = a[i] - 48; i < a.size(); i++, k = a[i] - 48 ) {
- while(k--) c = c + b; // ith digit is k, so, we add k times
- b.a.insert(b.a.begin(), '0'); // multiplied by 10
- }
- return c.normalize(sign * b.sign);
- }
- Bigint operator / ( Bigint b ) { // division operator overloading
- if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 );
- Bigint c("0"), d;
- for( int j = 0; j < a.size(); j++ ) d.a += "0";
- int dSign = sign * b.sign;
- b.sign = 1;
- for( int i = a.size() - 1; i >= 0; i-- ) {
- c.a.insert( c.a.begin(), '0');
- c = c + a.substr( i, 1 );
- while( !( c < b ) ) c = c - b, d.a[i]++;
- }
- return d.normalize(dSign);
- }
- Bigint operator % ( Bigint b ) { // modulo operator overloading
- if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 );
- Bigint c("0");
- b.sign = 1;
- for( int i = a.size() - 1; i >= 0; i-- ) {
- c.a.insert( c.a.begin(), '0');
- c = c + a.substr( i, 1 );
- while( !( c < b ) ) c = c - b;
- }
- return c.normalize(sign);
- }
- // output method
- void println() {
- if( sign == -1 ) putchar('-');
- for( int i = a.size() - 1; i >= 0; i-- ) putchar(a[i]);
- putchar('\n');
- }
- };
- Bigint dp[Mx][Max];
- int main(void) {
- #ifndef ONLINE_JUDGE
- READ("input.txt");
- #endif
- int tcase, caseNo = 0;
- SDi(tcase);
- getc(stdin);
- while(tcase--) {
- gets(X);
- gets(Z);
- length = strlen(Z);
- n = strlen(X);
- // complete search and got TLE
- // total = 0;
- // solve(0, 0);
- // println(total);
- Bigint zero = Bigint("0");
- Bigint one = Bigint("1");
- //as a non-empty substring of the subsequence cannot appear in an empty string
- FOR(i, 1, length) dp[i][0] = zero;
- // as the null string appears once in any string
- FOR(i, 0, n) dp[0][i] = one;
- FOR(i, 1, length)
- FOR(j, 1, n)
- if(Z[i - 1] == X[j - 1])
- dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1]; // 1 new match for every occurence of Z1...Zi in X1...Xj
- else
- dp[i][j] = dp[i][j - 1]; // No new occurence, so copy previous value
- dp[length][n].println();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement