Re: Pattern Matching

Ich konnte, den Text, alleine, ohne Tabelle von 1024 Byte = 1kByte auf 202 Byte schrumpfen

david@works:~\$ ./a.out
0: 0 A
1: 1 B
2: 2 C
3: 0 b
4: 3 a
5: 3 a
6: 5 b
7: 3 b
8: 7 b
9: 4 a
10: 6 b
11: 4 b
12: 11 b
13: 9 a
14: 5 a
15: 14 b
16: 12 a
17: 14 a
18: 10 b
19: 7 a
20: 17 b
21: 8 a
22: 6 a
23: 18 b
24: 11 a
25: 15 a
26: 22 b
27: 9 b
28: 13 b
29: 21 b
30: 24 b
31: 29 a
32: 26 a
33: 25 b
34: 13 a
35: 15 b
36: 24 a
37: 20 a
38: 17 a
39: 10 a
40: 20 b
41: 19 b
42: 28 a
43: 35 b
44: 30 b
45: 8 b
46: 45 b
47: 41 b
48: 44 a
49: 33 b
50: 19 a
51: 33 a
52: 32 b
53: 45 a
54: 37 b
55: 34 a
56: 26 b
57: 53 a
58: 39 b
59: 41 a
60: 23 b
61: 27 b
62: 36 b
63: 21 a
64: 38 a
65: 43 a
66: 51 b
67: 62 b
68: 27 a
69: 40 b
70: 68 a
71: 39 a
72: 54 b
73: 50 b
74: 55 b
75: 74 a
76: 64 b
77: 73 b
78: 31 a
79: 23 a
80: 18 a
81: 25 a
82: 64 a
83: 40 a
84: 32 a
85: 35 a
86: 72 a
87: 60 a
88: 58 b
89: 36 a
90: 38 b
91: 89 a
92: 83 b
93: 42 a
94: 69 a
95: 81 b
96: 63 b
97: 68 b
98: 53 b
99: 73 a
100: 76 a
101: 37 a
102: 100 b
103: 63 a
104: 22 a
105: 104 a
106: 88 b
107: 96 a
108: 49 a
109: 101 a
110: 105 a
111: 43 b
112: 97 b
113: 12 b
114: 48 b
115: 47 b
116: 96 b
117: 116 a
118: 105 b
119: 99 a
120: 87 b
121: 16 a
122: 101 b
123: 55 a
124: 100 a
125: 52 b
126: 103 b
127: 42 b
128: 47 a
129: 71 a
130: 90 a
131: 111 b
132: 113 a
133: 120 a
134: 58 a
135: 95 b
136: 116 b
137: 136 a
138: 90 b
139: 98 b
140: 46 a
141: 138 a
142: 83 a
143: 130 a
144: 65 a
145: 111 a
146: 80 a
147: 94 b
148: 115 a
149: 52 a
150: 54 a
151: 108 a
152: 80 b
153: 89 b
154: 113 b
155: 29 b
156: 112 a
157: 138 b
158: 139 a
159: 85 b
160: 31 b
161: 128 a
162: 104 b
163: 28 b
164: 93 b
165: 163 a
166: 66 a
167: 81 a
168: 110 b
169: 61 a
170: 168 b
171: 140 b
172: 154 b
173: 119 a
174: 122 a
175: 146 a
176: 85 a
177: 146 b
178: 172 a
179: 159 a
180: 147 b
181: 59 b
182: 78 a
183: 71 b
184: 16 b
185: 161 b
186: 107 b
187: 169 b
188: 70 a
189: 86 a
190: 142 b
191: 114 b
192: 112 b
193: 154 a
194: 167 b
195: 99 b
196: 140 a
197: 175 b
198: 91 a
199: 56 a
200: 49 b
201: 114 a
202: 79 b
203: 188 a
204: 159 b
A, A
B, B
C, C
b, Ab
ba, ba
a, ba
ab, ab
bb, bb
bbb, bbb
baa, baa
abb, abb
bab, bab
babb, babb
baaa, baaa
aa, aa
aab, aab
babba, babba
aaa, aaa
abbb, abbb
bba, bba
aaab, aaab
bbba, bbba
aba, aba
abbbb, abbbb
baba, baba
aaba, aaba
abab, abab
baab, baab
baaab, baaab
bbbab, bbbab
babab, babab
bbbaba, bbbaba
ababa, ababa
aabab, aabab
baaaa, baaaa
aabb, aabb
babaa, babaa
aaaba, aaaba
aaaa, aaaa
abba, abba
aaabb, aaabb
bbab, bbab
baaaba, baaaba
aabbb, aabbb
bababb, bababb
bbbb, bbbb
bbbbb, bbbbb
bbabb, bbabb
bababba, bababba
aababb, aababb
bbaa, bbaa
aababa, aababa
ababab, ababab
bbbba, bbbba
aaabab, aaabab
baaaaa, baaaaa
ababb, ababb
bbbbaa, bbbbaa
abbab, abbab
bbaba, bbaba
abbbbb, abbbbb
baabb, baabb
babaab, babaab
bbbaa, bbbaa
aaaaa, aaaaa
aabbba, aabbba
aababab, aababab
babaabb, babaabb
baaba, baaba
aaabbb, aaabbb
baabaa, baabaa
abbaa, abbaa
aaababb, aaababb
bbaab, bbaab
baaaaab, baaaaab
baaaaaba, baaaaaba
aaaaab, aaaaab
bbaabb, bbaabb
bbbabaa, bbbabaa
abbbba, abbbba
abbba, abbba
aabaa, aabaa
aaaaaa, aaaaaa
aaabba, aaabba
ababaa, ababaa
aabba, aabba
aaababba, aaababba
abbbbba, abbbbba
abbabb, abbabb
babaaa, babaaa
aaaab, aaaab
babaaaa, babaaaa
aaabbab, aaabbab
baaabaa, baaabaa
aaabbba, aaabbba
aabaab, aabaab
bbbaab, bbbaab
baabab, baabab
bbbbab, bbbbab
bbaaba, bbaaba
aaaaaba, aaaaaba
aaabaa, aaabaa
aaaaabab, aaaaabab
bbbaaa, bbbaaa
abaa, abaa
abaaa, abaaa
abbabbb, abbabbb
bbbaaba, bbbaaba
aababba, aababba
aaabaaa, aaabaaa
abaaaa, abaaaa
aabbbb, aabbbb
baababb, baababb
babbb, babbb
bababbab, bababbab
bbabbb, bbabbb
bbbaabb, bbbaabb
bbbaabba, bbbaabba
abaaab, abaaab
bbaabaa, bbaabaa
abbbbbab, abbbbbab
babbaa, babbaa
aaabaab, aaabaab
baaaaaa, baaaaaa
aaaaabaa, aaaaabaa
abababb, abababb
bbbaaab, bbbaaab
baaabab, baaabab
bbabba, bbabba
abbaaa, abbaaa
aaaaba, aaaaba
aabbbbb, aabbbbb
babbba, babbba
abbbbbaba, abbbbbaba
abbaba, abbaba
aabaabb, aabaabb
bbbaabbb, bbbaabbb
bbbaabbba, bbbaabbba
aaaabb, aaaabb
bbbbabb, bbbbabb
bbbbba, bbbbba
aaaabba, aaaabba
aaabbaa, aaabbaa
aaaabaa, aaaabaa
aabbbaa, aabbbaa
aabbbba, aabbbba
abbbaa, abbbaa
aaabbbab, aaabbbab
bbabbba, bbabbba
abababa, abababa
aaababa, aaababa
aababbaa, aababbaa
abbbab, abbbab
babaaab, babaaab
babbbb, babbbb
bbbabb, bbbabb
baababba, baababba
aaaabbb, aaaabbb
bbbbabba, bbbbabba
aabbab, aabbab
bbbabab, bbbabab
bbabbaa, bbabbaa
abaab, abaab
baaabb, baaabb
baaabaab, baaabaab
baaabba, baaabba
aabababa, aabababa
aabaaa, aabaaa
abaaaab, abaaaab
baabba, baabba
abaaaabb, abaaaabb
bbbbbab, bbbbbab
babbbbb, babbbbb
bbaabaaa, bbaabaaa
aaabaaba, aaabaaba
abbbaaa, abbbaaa
aabbaa, aabbaa
abbbaab, abbbaab
babbbbba, babbbbba
aabbaba, aabbaba
aaabbbabb, aaabbbabb
bbabab, bbabab
bbbabaaa, bbbabaaa
abbaab, abbaab
babbab, babbab
bbabbaab, bbabbaab
bbbaabab, bbbaabab
baabbab, baabbab
baabaaa, baabaaa
aaababbaa, aaababbaa
aaabbaab, aaabbaab
bababbabb, bababbabb
baababbb, baababbb
babbbba, babbbba
aabaaab, aabaaab
bbaabab, bbaabab
bbbbbaa, bbbbbaa
abbbaaab, abbbaaab
babaaaaa, babaaaaa
ababba, ababba
aababbb, aababbb
bababbaba, bababbaba
abbbbab, abbbbab
baabaaaa, baabaaaa
aabbabb, aabbabb
text: 1024
coded: 202
david@works:~\$

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

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

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 [1024*64];
    int coded [1024*64];
    int x;

    srand (0);

    for (i = 0;  i < 1024;  i++)
      text [i] = (rand () % ('c'-'a')) + 'a';
    text [i] = 0;

    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]);
    }

    printf ("text: %in", strlen (text));
    printf ("coded: %in", x);

return 0;
}