Karp&Rabin Algorithmus

[marabu]

Zitat von Der_Unwissende:

ehrlich gesagt liegt Theoretische Informatik schon etwas zurück

Was soll ich denn da erst sagen...

Zitat von Der_Unwissende:

es müsste sich eigentlich eher um einen Algorithmus handeln, der sehr effizient die Position eines Teilstrings liefert.

Volltreffer.

Zitat von Der_Unwissende:

Ist glaube ich auch kein ganz trivialer Algorithmus gewesen.

Eher doch, würde ich sagen.

[equote="Sedgewick schreibt in 'Algorithms' zum Thema 'String Searching'"]... In 1980 R. M. Karp and M. O. Rabin ... came up with an algorithm almost as simple as the brute-force algorithm ... Furthermore, their algorithm extends easily to two-dimensional patterns and text, which makes it more useful than the others for picture processing.[/equote]
Hier noch ein Link für eine C-Implementierung (1-dimensional): klick

Grüße vom marabu