Re: Pattern Matching

Mit komprimierter Tabelle, sieht gut aus

#include <stdio.h>
#include <string.h>

char table [1024][1024];
char tabledst [1024][1024];
int itable [1024];
int ctable [1024];

int strnmcmp (char *src, char *des, int m, int n) {
  int i, j;
  for (i = m, j = 0;  i <= n; i++, j++)
    if (src [j] != des [i])
      return -1;
return 0;
}

//  strncat (p, src+m, n-m);

int main (void) {
    int ch;
    int i, j, k, n, length, notice;
    int c;
    char text [] = "ABBACABABBAAACCAACAACACACBBBBACAABACBBABABCA";
    int coded [256*128];
    int x;

    for (n = 'A' - 'A';  n < ('C' - 'A')+1;  n++) {
      table [n][0] = n + 'A';
      table [n][1] = 0;
      ctable [n] = n + 'A';
      itable [n] = n;
    }


    for (i = 0, x = 0, j = 1, length = 1;  i < strlen (text)+1; ) {
      for (length = 1; (i + length) < strlen (text)+1; ) {
        for (k = 0;  (k < n) \&amp;\&amp; (strncmp (table [k], text+i, length) != 0);  k++);
        if (k >= n) {
          coded [x] = notice;
          x++;
          itable [n] = notice;
          ctable [n] = text[i + length-1];
          strncpy (table [n], text+i, length);
          n++;
          length--;
          break;
        }
        else if (k < n) {
          notice = k;
          length++;
        }
      }
      i = i + length;
    }

    for (i = 0;  i < n;  i++) {
      printf ("%i: %i %cn", i, itable [i], ctable [i]);
    }

   for (i = 0;  i < n;  i++) {
      if (itable [i] == i) {
        tabledst [i][0] = ctable [i];
        tabledst [i][1] = 0;
      }
      else {
        strcpy (tabledst [i], table [itable[i]]);
        tabledst [i][j = strlen(tabledst[i])+0] = ctable [i];
        tabledst [i][j+1] = 0;
      }
    }

    for (i = 0;  i < n;  i++) {
      printf ("%s, %sn", table [i], tabledst [i]);
    }




return 0;
}

david@works:~\$ gcc lempelziv5.c
david@works:~\$ ./a.out
0: 0 A
1: 1 B
2: 2 C
3: 0 B
4: 1 B
5: 1 A
6: 0 C
7: 2 A
8: 3 A
9: 3 B
10: 5 A
11: 0 A
12: 6 C
13: 7 A
14: 6 A
15: 11 C
16: 7 C
17: 16 B
18: 4 B
19: 4 A
20: 14 A
21: 8 C
22: 2 B
23: 19 B
24: 5 B
25: 1 C
A, A
B, B
C, C
AB, AB
BB, BB
BA, BA
AC, AC
CA, CA
ABA, ABA
ABB, ABB
BAA, BAA
AA, AA
ACC, ACC
CAA, CAA
ACA, ACA
AAC, AAC
CAC, CAC
CACB, CACB
BBB, BBB
BBA, BBA
ACAA, ACAA
ABAC, ABAC
CB, CB
BBAB, BBAB
BAB, BAB
BC, BC
david@works:~\$