wdmatch — Word Match Subsequence

Allowed functions: write

Write a program that takes two strings and checks whether it's possible to write the first string with characters from the second string, while respecting the order in which these characters appear in the second string.

If it's possible, the program displays the string, followed by a newline, otherwise it simply displays a newline. If the number of arguments is not 2, the program displays a newline.

Examples

$>./wdmatch "faya" "fgvvfdxcacpolhyghbreda" | cat -e
faya$
$>./wdmatch "faya" "fgvvfdxcacpolhyghbred" | cat -e
$
$>./wdmatch "quarante deux" "qfqfsudf arzgsayns tsregfdgs sjytdekuoixq " | cat -e
quarante deux$
$>./wdmatch "error" rrerrrfiiljdfxjyuifrrvcoojh | cat -e
$
$>./wdmatch | cat -e
$

Solution

Download wdmatch.c

#include <unistd.h>

int main(int c, char **v) {
	if (c != 3) {
		write(1, "\n", 1);
		return 0;
	}

	int i = 0;
	int j = 0;

	while (v[1][i] && v[2][j]) {
		if (v[1][i] == v[2][j])
			i++;

		j++;
	}

	if (v[1][i] == '\0') {

		write(1, v[1], i);
	}

	write(1, "\n", 1);
	return 0;
}

How It Works

Goal: Check if the first string is a subsequence of the second string, and print it if so.

Approach: Use two pointers -- one for each string -- advancing the second pointer every step and the first only when characters match.

Step by step:

1. If the argument count is not 3, print a newline and exit.
2. Initialize pointer i for v[1] (the word to match) and j for v[2] (the source string).
3. Loop while both strings have characters left: if v[1][i] == v[2][j], advance i; always advance j.
4. After the loop, if v[1][i] is the null terminator, every character was found in order -- print the word.
5. Print a trailing newline.

Key concept: The two-pointer subsequence technique -- one pointer greedily scans the haystack while the other tracks progress through the needle.