c - 如何将字符串分隔成唯一字符/字符串的数组

Question

基本上我想知道是否有可能(如果可以的话)从左到右读取一个字符串并贪婪地终止并在找到新字符串后追加。例如。

“ABCABCABCABC”会给出{“A”“B”“C”“AB”“CA”“BC”“ABC”

我一整天都在尝试，但我最终得到的只是损坏的代码和崩溃的程序。

这就是我所拥有的不起作用的东西。该数组定义为 *a[linelen]

for(i =0; i < linelen ;i++)
{
    j=0;
    k=0; 
    tempstr[j] = input[i]; // move character from input to tempstring 
        for(k=0; k< array_size; k++) //search through array
        {
            tempstr[j] = input[i];
            if(*a != tempstr)//(strcmp(a,tempstr)) != 0) // if str not in array
            {
                printf("%s\n", a[0]); //debug
                a[array_size] = tempstr;
                //strcpy(a[array_size], tempstr); //copy str into array
                array_size++;
                memset(tempstr,0,linelen-i); // reset tempstr to empty
                j=0;

            } 
            if( *a == tempstr)//(strcmp(a[array_size],tempstr)) == 0)
            {
                j++;
                tempstr[j] = input[i+1];
                if(i != linelen -1) // otherwise if tempstr already in array
                {
                    printf("%s\n",a[0]); //debug
                    j++;
                    tempstr[j] = input[i+1];
                }
                else if (i == linelen -1) // if it is the last letter
                {
                    a[array_size] = tempstr;
                    //strcpy(a[array_size], tempstr); // add to array
                    break;
                }

            }
        }

}

Answer 1

下面是一个使用简单字符数组来存储“已见”字符串的方法:

#include <stdio.h>

#if 0
#define dbg(_fmt...)        printf(_fmt)
#else
#define dbg(_fmt...)        /**/
#endif

// NOTE: could be char * and realloc if necessary
char seen[5000];

// find -- find old string
// RETURNS: 1=found, 0=no match
int
find(char *str)
{
    char *lhs;
    char *rhs;
    int foundflg;

    dbg("find: str='%s'\n",str);

    rhs = str;
    lhs = seen;
    dbg("find: lhs='%s'\n",seen);

    foundflg = 0;
    for (;  lhs < str;  ++lhs, ++rhs) {
        dbg("find: TRY lhs='%s' rhs='%s'\n",lhs,rhs);

        if (*lhs != *rhs) {
            dbg("find: SKIP\n");
            for (;  *lhs != 0;  ++lhs);
            rhs = str - 1;
            continue;
        }

        if ((*lhs == 0) && (*rhs == 0)) {
            dbg("find: MATCH\n");
            foundflg = 1;
            break;
        }

        if (*rhs == 0)
            break;
    }

    return foundflg;
}

void
sepstr(const char *inp)
{
    int chr;
    char *lhs;
    char *rhs;
    int finflg;

    lhs = seen;
    rhs = seen;
    finflg = 0;

    for (chr = *inp;  chr != 0;  chr = *++inp) {
        *rhs++ = chr;
        *rhs = 0;

        if (find(lhs)) {
            finflg = 1;
            continue;
        }

        printf("%s\n",lhs);
        lhs = ++rhs;
        finflg = 0;
    }

    if (finflg)
        printf("%s\n",lhs);
}

int
main(int argc,char **argv)
{

#if 1
    sepstr("ABCABCABCABC");
#else
    sepstr("ABCABCABCABCABC");
#endif
}

第二种方法:

#include <stdio.h>

char out[500];

#ifdef BIG
#define SEEN 256
#else
#define SEEN (26 + 1)
#endif

char seen[SEEN][SEEN];

void
sepstr(const char *inp)
{
    int chr;
    char *prv;
    char *rhs;

    prv = seen[0];

    rhs = out;
    for (chr = *inp;  chr != 0;  chr = *++inp) {
        *rhs++ = chr;

#ifndef BIG
        chr = (chr - 'A') + 1;
#endif

        if (prv[chr]) {
            prv = seen[chr];
            continue;
        }

        *rhs = 0;
        printf("%s\n",out);

        prv[chr] = 1;
        rhs = out;
        prv = seen[0];
    }

    if (rhs > out) {
        *rhs = 0;
        printf("%s\n",out);
    }
}

int
main(void)
{

#if 1
    sepstr("ABCABCABCABC");
#else
    sepstr("ABCABCABCABCABC");
#endif

    return 0;
}

这里是大家程序的一些基准(时间在 ns 和 printf nop'ed):

       first      minimum author         527          137 craig1 -- original -- uses single seen char array         146           39 craig2 -- modified -- uses 2D seen table       45234        45234 felix1 -- original -- may only be executed once       40460          656 felix2 -- uses fixed input          24           18 machine1 -- original -- uses buffer[20][20] on stack         908          417 machine2 -- modified -- uses global buffer[20][20]       43089         1120 milevyo1 -- original       42719          711 milevyo2 -- parseString tmp is stack buffer no malloc        7957          429 milevyo3 -- NewNode uses fixed pool no malloc        7457          380 milevyo4 -- removed linked list