* nma2818@vip.cybercity.dk
> Hej NG: Jeg sidder lige og udfærdiger mit første windows program som
> er en text editor. Nu har jeg bare et spørgsmål. Hvordan søger man
> efter en tekst inde i en anden tekst. Altså jeg skal til at lave søg
> funktionen hvor brugeren kan søge efter en tekst der herefter bliver
> markeret.
Hehe, du kunne ikke stille et litt _enklere_ spørsmål, hva?
Det finnes _mange_ måter å lete etter tekst på. La oss begynne med
temmelig enkle:
* I C, dersom representasjonen av teksten din er via char[]/char*, så
kan du bruke strstr
(<URL:
http://www.dinkumware.com/htm_cl/string.html#strstr>). Den er
veldig enkelt, men dette holder mer enn nok i en rekke tilfeller
* I C++, dersom representasjonen av teksten din er via std::string, så
kan du bruke std::basic_string::find.
I begge tilfellene over finnes det varianter som søker etter mønsteret
bakfra såvel som forfra.
Dersom du har andre representasjoner for teksten, kan du fortelle om
dem, slik at man kan gi et bedre råd.
Hvis det viser seg at disse (ganske enkle) metoder ikke er
tilstrekkelig, finnes det en rekke andre muligheter:
* regulære uttrykk (regular expressions). Man vil oftest _IKKE_
implementere dette selv. Det finnes en rekke biblioteker som fikser
sånt (ta en titt på <URL:
http://www.boost.org/> eller
<URL:
http://www.trumphurst.com/cpplibs/>). Vær forøvrig klar over at
regexps er ofte feil måte å gjøre ting på. Man burde vite først og
fremst hva de ikke kan og anvende dem deretter. Men passer
sannsynligvis i konteksten din.
* Dersom en plain-vanilla algoritme slik skissert over ikke duger,
finnes det en _mengde_ av (temmelig) avanserte algoritmer som prøver
å uttnytte visse egenskaper som ligger i teksten/mønstre man leter
etter. En algoritmebook er sikkert ikke å forakte, men du kan ta en
titt på denne artikkelen som en kort intro:
<URL:
http://www-igm.univ-mlv.fr/~lecroq/string/>. Hvorvidt det er et
poeng i å implementere noe slikt er at stort spørsmål (rent
teoretisk liker jeg ideen å kunne søke etter et _vilkårlig_ mønster
i O(<lengde av inputen>), men jeg er litt rar).
* Som tittelen på den forrige artikkelen antyder finnes det algoritmer
som gjør et ikke-eksakt søk etter det spesifiserte mønsteret (Pike
har fx. "fuzzymatch"). Heller ikke her har man lyst til å
implementere dette selv, men noen har sikkert skrevet et bibliotek
som gjør nettopp noe slikt
Det kan kanskje lønne seg å bruke andre, helt spesielle teknikker. En
mulighet er å hash'e alle ord i teksten, og huske på linjenumre for så
å hash'e inputmønsteret og prøve å komme med forslag derifra. Det
finnes også andre muligheter for å preprosessere input'en på en
passende måte (jeg husker vi laget en hash og et BST for å lage en
slags ordbok/stavekontroll). Dersom teksten man leter i har bestemte
egenskaper (fx. en ordbok), kan det lønne seg å bruke helt spesielle
datastrukturer:
<URL:
http://www.ddj.com/articles/1998/9804/9804a/9804a.htm?topic=algoritms>.
Igjen, hvorvidt det er et poeng i å gjøre det kommer an på
hvilken tekst man søker i og hvorfor man gjør dette.
ivr
--
Besides, meat tends to run away when possible, or fights. Either
response presents behavioral challenges too complex for any existing
robot.
-- Stuart Wilkinson, inventor of the "gastrobot"