Hallo,
ich hab nen problem, wo es mir gerade schwer fällt, dass programmiertechnisch umzusetzen.
folgende ausgangssituation:
- wir haben einen String/Sequenz S mit länge |S|.
- wir haben ein Alphabet ∑ mit |∑| = 20
- wir haben einen Paramater wortlänge |w|
im programm sollen dann alle substrings von S mit länge |w| gebildet werden (kein problem).
dann sollen alle möglichen kombinationen an wörtern aus ∑ mit länge |w| gebildet (also |∑|^|w| kombinationen) und mit dem substring von S verglichen werden - wonach oder wie verglichen wird, ist uninterssant.
die frage ist nun, wie erstelle ich alle möglichen kombinationen. wäre |w| fest, wäre das ganze ja kein problem.
bei |w| = 2 würde man einfach zwei for-schleifen ineinander schachteln und so alle möglichkeiten durchgehen, bei |w| = 3 halt drei for-schleifen. in der innersten schleife würde dann der vergleich durchgeführt werden.
außerdem frage ich mich, ob es sinnvoll wäre, alle möglichen wörter vorher zu erzeugen und abzuspeichern, damit diese nicht für alle möglichen substrings (|S| - |w|) immer wieder neu erstellt werden müssen.
kritisch zu betrachten wäre hier der speicheraufwand, denn für |w| = 4 wären es immerhin schon 160000 kombinationen. aber es wäre auch genauso schlecht, die jedes mal wieder für einen neuen substring neu zu erstellen, was die laufzeit betrifft. gibts da nen guten kompromiss zwischen speicheraufwand und laufzeit?
ps: ich schreib im übrigen in java... vielleicht gibt es hier ja ein paar nützliche klassen oder funktionen, die mir bei der umsetzung helfen könnten.
