[UVa - 10069] Distinct Subsequences

Problem

A subsequence of a given sequence is just the given sequence with some elements (possibly none) left out. Formally, given a sequence X = x1x2 . . . xm, another sequence Z = z1z2 . . . zk is a subsequence of X if there exists a strictly increasing sequence < i1, i2, . . . , ik > of indices of X such that for all j = 1, 2, . . . , k, we have xij = zj . For example, Z = bcdb is a subsequence of X = abcbdab with corresponding index sequence < 2, 3, 5, 7 >. In this problem your job is to write a program that counts the number of occurrences of Z in X as a subsequence such that each has a distinct index sequence.

 

Input

The first line of the input contains an integer N indicating the number of test cases to follow. The first line of each test case contains a string X, composed entirely of lowercase alphabetic characters and having length no greater than 10,000. The second line contains another string Z having length no greater than 100 and also composed of only lowercase alphabetic characters. Be assured that neither Z nor any prefix or suffix of Z will have more than 10100 distinct occurrences in X as a subsequence.

 

Output

For each test case in the input output the number of distinct occurrences of Z in X as a subsequence. Output for each input set must be on a separate line.

 

//Input_1.txt
2
babgbag
bag
rabbbit
rabbit

//Output_1.txt
5
3

 

//Input_2.txt
gfggfg
gg
gggggg
gg
abcde
aed

//Output_2.txt
6
15
0

 

//Input_3.txt
bbklge
lgeb
rabbit
rabbitt
banana
ban

//Output_3.txt
0
0
3

 

//Input_4.txt
geeksforgeeks
ge
moonnekky
monkey

//Output_4.txt
6
0

 

//Input_5.txt
abcbbcc
abc
asubsequenceofagivenstringisastringthatwearchivebydeletingsomecharactersorpossiblezerocharactersalsofromtheoriginalstringwecantchangetheorderoftheelementspresentintheoriginalstring
a
everysubstringisasubsequencebuteverysubsequenceisnotasubstring
subsequence

//Output_5.txt
7
28
287

 

 

Solution

#define _CRT_SECURE_NO_WARNINGS
#define NUMBER_OF_FILES 5
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char x[10001];
char z[101];
int result[10];

int Algorithm(int i) {
	char Input[5][15] = {
		"Input_1.txt", "Input_2.txt", "Input_3.txt", "Input_4.txt", "Input_5.txt"
	};
	char Output[5][15] = {
		"Output_1.txt", "Output_2.txt", "Output_3.txt", "Output_4.txt", "Output_5.txt"
	};

	int dp[100][100];

	FILE* input;
	input = fopen(Input[i], "r");

	FILE* output;
	output = fopen(Output[i], "w");

	int number_of_sets, result;

	if (input != NULL) {
		int a = fscanf(input, "%d", &number_of_sets);
		for (int i = 0; i < number_of_sets; i++) {
			a = fscanf(input, "%s", &x);
			a = fscanf(input, "%s", &z);
			dp[0][0] = 1;
			for (int i = 0; i <= strlen(z); i++) {
				dp[i][0] = 0;
			}
			for (int i = 0; i <= strlen(x); i++) {
				dp[0][i] = 1;
			}
			for (int i = 1; i <= strlen(z); i++) {
				for (int j = 1; j <= strlen(x); j++) {
					dp[i][j] = dp[i][j - 1];
					if (z[i - 1] == x[j - 1]) {
						dp[i][j] += dp[i - 1][j - 1];
					}
				}
			}
			fprintf(output, "%d\n", dp[strlen(z)][strlen(x)]);
		}
	}
	else {
		printf("Error.");
		exit(1);
	}

	fclose(input);
	return number_of_sets;
}


int main(void) {
	for (int i = 0; i < NUMBER_OF_FILES; i++) {
		Algorithm(i);
	}
}