V
Mr. B schrieb:
Soweit ich gelesen habe, gibt es zwei Möglichkeiten, das zu bewerkstelligen.
stimmt. man kann nur boyer-moore und abwandlungen nehmen oder endliche automaten. funktionen aus <algrithm> oder <cstring> funktionieren nicht. regexps auch nicht. inline-assembler mit repne-befehlen oder kleine selbergebaute schleifen sind zu einfach und schleifen om strcpy oder memcpy sind zu schmuddelig. hashen gilt als fahrlässig und wurde bei der letzten welteliteprogrammiererkonferenz sogar verboten.
und da du von nem großen zu durchsuchenden string sprichst, liegt ja eh boyer-moore nahe. am liebsten mag ich die abwandlung, die neulich in der c't stand. (neulich so um mitte 2000).
#ifndef VHLIB_TEXTSEARCH_H
#define VHLIB_TEXTSEARCH_H
#pragma once
// Verfahren aus einer c't übernommen
class TextSearch
{
private:
int shift[256];
int look_at;
char *pattern;
int patternlen;
char *end;
char *pos;
char *find(char *text);
public:
TextSearch(char *p,int m);
~TextSearch();
char *findFirst(char *text,int size);
char *findNext();
};
#endif
#include "TextSearch.h"
#include <string.h>
TextSearch::TextSearch(char *p,int m)
{
patternlen=m;
pattern=new char[m];
memcpy(pattern,p,m);
int i;
for(i=0;i<256;++i)
shift[i]=m+1;
for(i=0;i<m;i++)
shift[(unsigned char)pattern[i]]=m-i;
look_at=0;
while(look_at<m-1)
{
if(p[m-1]==p[m-(look_at+2)]) break;
++look_at;
};
};
TextSearch::~TextSearch()
{
delete[] pattern;
};
char *TextSearch::findFirst(char *text,int size)
{
end=text+size;
return pos=find(text);
};
char *TextSearch::findNext()
{
return pos=find(pos+1);
};
char *TextSearch::find(char *text)
{
int i;
char *t=text;
for(;;)
{
i=patternlen-1;
if(t+i>=end) return 0;
while(t[i]!=pattern[i])
{
t+=shift[(unsigned char)t[patternlen]];
if(t+i>=end) return 0;
}
--i;
while(t[i]==pattern[i])
{
if(--i<0) return t;
}
t+=look_at+shift[(unsigned char)t[patternlen+look_at]];
}
}
