# 50171. Split a string

## I'm a slow walker, but I never walk backwards.

We want to split a string into tokens and map the address of each token to $n$ character pointer arrays.

We will be given a pointer ptr, which points to an array of $n$ pointers $A$ that ends with NULL. Each element of this pointer array $A$ points to another pointer array $A_1$, $A_2$, ... $A_n$, whose elements point to different tokens within a given string str. The string str contains lowercase alphabets and the delimiter *.

First we split string str with the delimiter * into tokens with strtok, so that every token ends with a '\0'. Then we assign the address of all tokens, in the order they appear in str and one at a time, to the $A_i$ having the minimum total number of characters. If there are more than one $A_i$ having the minimum total number of characters, we choose the one with the smallest index. Finally we end every $A_i$ with a NULL.

The pointer arrays are linked as shown in the following animation when str is abc*de**f*gh***ij*k, and there are four pointer arrays.

The prototype of the function splitAndMap is given by splitAndMap.h as follows.

void splitAndMap(char*** ptr, char* str);


You can use the following main.c to test your function.

#include <stdio.h>#include <stdlib.h>#include <string.h>#include "splitAndMap.h"#define numPtrArray 4#define MAXLEN 400000int main(){    char*** ptr = malloc((numPtrArray+1) * sizeof(char**));    for(int i=0; i<numPtrArray; i++){        ptr[i] = malloc(MAXLEN * sizeof(char**));    }    ptr[numPtrArray] = NULL;     char str[MAXLEN];    scanf("%s", str);     splitAndMap(ptr, str);     for(int i=0; i<numPtrArray; i++){        for(int j=0; ptr[i][j]!=NULL; j++)            printf("%s ", ptr[i][j]);        printf("\n");    }     for(int i=0; i<numPtrArray; i++) free(ptr[i]);    free(ptr);    return 0;}


Note that the number of pointer arrays ($n$) is from 1 to 10. Also you should not use too much memory or you will get MLE.

## Input Format (for the test main.c)

The input is a string that contains lowercase alphabets and the delimiter *. The length of the string is between 1 and 400000.

## Output Format (for the test main.c)

The outputs are the tokens in all pointer arrays, in increasing index order, and within a pointer array the token will appear in the order is they are added into the pointer array.

## Sample Input 1 (for the test main.c)

abc*de**f*gh***ij*k


## Sample Output 1 (for the test main.c)

abcde kf ijgh


## Sample Input 2 (for the test main.c)

jwgt*lwg*it*m*qrje*bis*kj*o


## Sample Output 2 (for the test main.c)

jwgt olwg kjit bism qrje


## Sample Input 3 (for the test main.c)

a*aa**aa*a*bb*bb******bb*bb*aa*aa*aa**aa*bb*bb*****bb*bb*aa*aa*a*a


## Sample Output 3 (for the test main.c)

a bb aa bb aaaa bb aa bb aaa bb aa bb aa bb aa bb aa