Hello from TASTEDEV,
We would like to introduce TASTEREMOTE, a remote desktop project that lets you view and control a remote computer through a web browser. Install the host app on the PC you want to access, then connect from a browser without installing a separate viewer app. You can use the TASTEDEV-operated server or run your own server.
TASTEREMOTE is under active development as we continue to improve its features and stability. Depending on your setup, you may encounter bugs or features that are not yet fully polished. Please review the supported operating systems and known limitations before getting started.
If you run into a problem or have feedback, please leave a comment or question on the product page. Including your operating system, TASTEREMOTE version, and the steps that led to the issue will help us investigate and improve the project.
Product and downloads: https://tastedev.net/products/remote
Documentation: https://tastedev.net/docs/remote
For setup instructions and development updates, follow the development log through the Learn more link below.
There is still work to do, and your feedback will help us improve TASTEREMOTE step by step. Thank you for your interest, for trying the project, and for sharing your experience with us.
The TASTEDEV Team
Zeichenkettenalgorithmen vergleichen und durchsuchen Folgen von Zeichen schnell und korrekt. Das zentrale Problem ist die Mustersuche, also alle Stellen zu finden, an denen ein kurzes Muster in einem langen Text vorkommt. Auch die Suche nach allen Wörtern eines Wörterbuchs mit einem bestimmten Präfix und die gleichzeitige Suche nach vielen Mustern gehören dazu. Der naive Ansatz, jede Position einzeln zu prüfen, braucht im schlimmsten Fall Zeit proportional zu Textlänge mal Musterlänge.
Die Suchfunktion im Editor, Logsuche, Autovervollständigung im Suchfeld, Angriffserkennung, Dateisynchronisation und Genomanalyse beruhen alle auf Zeichenkettenalgorithmen. KMP nutzt bereits durchgeführte Vergleiche über eine Fehlertabelle und garantiert lineare Laufzeit, Rabin-Karp schiebt einen rollenden Hash über den Text und spart so die meisten Vergleiche, und ein Trie teilt gemeinsame Präfixe, sodass eine Präfixsuche nur von der Wortlänge abhängt. Das Thema kommt außerdem häufig in Coding-Interviews vor.
Lernen Sie zuerst die Begriffe Präfix, Suffix und Rand und prüfen Sie von Hand, warum die naive Suche langsam ist. Berechnen Sie dann die Präfixfunktion für ein kleines Muster selbst, implementieren Sie die KMP-Suche und einen Trie und vergleichen Sie die Ergebnisse mit der Standardbibliothek. Zum Schluss lohnt sich ein Blick auf typische Fallen in der Praxis wie Hash-Kollisionen und Unicode-Normalisierung.
Besonderheiten
Präfixfunktion und KMP
Für jedes Präfix des Musters wird der längste Rand vorberechnet; bei einer Abweichung springt die Suche zu einem kürzeren Rand, ohne im Text zurückzugehen, und läuft in O(n + m).
Rollender Hash
Rabin-Karp aktualisiert den Hash jedes Fensters der Länge m in O(1), vergleicht ihn mit dem Hash des Musters und prüft die Zeichen nur bei gleichen Hashwerten.
Tries
Ein Baum, der Zeichen für Zeichen durchlaufen wird; gemeinsame Präfixe werden nur einmal gespeichert, daher hängen Präfixsuche und Autovervollständigung nur von der Wortlänge ab.
Z-Algorithmus und Unicode
Das Z-Array liefert für jede Position in linearer Zeit das längste gemeinsame Präfix mit der ganzen Zeichenkette. Bei echten Texten müssen Normalisierung und Indexeinheiten beachtet werden.
Einsatzgebiete
Suche im Editor und in Logdateien
Autovervollständigung und Wörterbücher
Angriffserkennung und Wortfilter
Dateisynchronisation und Genomanalyse
Referenzimplementierung
Referenzimplementierung: KMP-Suche
prefix_function berechnet den längsten Rand jedes Musterpräfixes, und kmp_search liest den Text mit dieser Tabelle genau einmal von links nach rechts und sammelt alle Startpositionen. Da k nach einem Treffer auf pi[k - 1] gesetzt wird, werden auch überlappende Vorkommen wie bei 0 und 2 gefunden. Mit python string_search.py werden beide Ergebnisse ausgegeben.
string_search.py
def prefix_function(p: str) -> list[int]:
"""pi[i] = length of the longest proper border of p[:i + 1]."""
pi = [0] * len(p)
k = 0
for i in range(1, len(p)):
while k > 0 and p[i] != p[k]:
k = pi[k - 1]
if p[i] == p[k]:
k += 1
pi[i] = k
return pi
def kmp_search(text: str, pattern: str) -> list[int]:
"""Start positions of every (possibly overlapping) occurrence."""
if not pattern:
return list(range(len(text) + 1))
pi = prefix_function(pattern)
hits, k = [], 0
for i, ch in enumerate(text):
while k > 0 and ch != pattern[k]:
k = pi[k - 1]
if ch == pattern[k]:
k += 1
if k == len(pattern):
hits.append(i - k + 1)
k = pi[k - 1]
return hits
if __name__ == "__main__":
print(prefix_function("ababaca")) # [0, 0, 1, 2, 3, 0, 1]
print(kmp_search("abababcabab", "abab")) # [0, 2, 7]
python string_search.py
Schritt-für-Schritt-Anleitung
Sechs Kapitel führen dich von der Installation bis zu den Kernkonzepten von Zeichenkettenalgorithmen.
0 Kommentare
Anmelden · Melde dich an, um einen Kommentar zu schreiben.