[C] Funktion zum Suchen schreiben [eilt, da für Schule]
-
ja ne das ist klar, aber der string den ich vergleiche, vergleiche ich doch byteweise, wie kann ich denn feststellen ob jedes byte identisch ist? denn ich vergleiche ja nicht nur ein einziges zeichen...
-
Mal ein Beispiel: wir suchen "def" in "abdcdefghi" okay?
'd' == 'a'? Ne, also ersten Index hochschieben.
'd' == 'b'? Ne, also ersten Index wieder hochschieben.
'd' == 'd'? Jo. Ersten Index nicht hochschieben, dafür jetzt den zweiten Index hochschieben: 'e' == 'c'? Ne? Zweiten Index wieder auf 0.
'd' == 'c'? Ne, also ersten index weiter hochschieben.
'd' == 'd'? Jo. Ersten Index nicht weiter hochschieben, dafür jetzt den zweiten Index hochschieben. 'e' == 'e'? Jo, zweiten Index weiter hochschieben. 'f'=='f'? Jo, zweiten Index weiter hochschieben. '\0' == 'g'? '\0' im zu suchenden String gefunden, also ein komplettes Match -> der erste Index gibt den Trefferindex an.Das ist jetzt so ganz stumpfsinnig eine Mustersuche.
-
na, du brauchst halt 2 schleifen ineinander
die erste geht die position im string durch und die zweite das suchwort. du vergleichst dann, ob alle bytes vom string und dem suchwort ab der position im string übereinstimmen. also string[stringPos + suchPos] == suchwort[suchPos]. Wenn du die innere Schleife ganz durchlaufen hast und alle bytes gleich waren hast du einen treffer. du musst natürlich auch noch die stringlängen beachten.
-
Daniel E. schrieb:
Das ist jetzt so ganz stumpfsinnig eine Mustersuche.
Um das von Daniel E. aufzugreifen, das es "eine" Mustersuche ist, was impliziert das es mehrere gibt, noch ein paar Schlagworte für eine Recherche, damit du auch ein bisschen was zu erzählen hast.
Boyer-Moore-Algorithmus
Knuth-Morris-Pratt-Algorithmus
Karp-Rabin-AlgorithmusDabei handelt es sich um drei der bekanntesten Algorithmen.
tt
-
DAnke für deinen Hinweis zu den Algorithmen, also der Tut es für unserere Schulsachen bestimmt ganz gut,
1 function NaiveSuche(string s[1..n], string sub[1..m])
2 for i from 1 to n
3 for j from 1 to m
4 if s[i+j-1] ≠ sub[j]
5 springe zur nächsten Iteration der äußeren Schleife
6 return i
7 return nicht gefundenjedoch kann ich mit der sprache nicht so viel anfangen, wie schreib ich das für CPP um?
-
hallo,
ok ich hab es jetzt mit C++ Strings hinbekommen. Das ging viel einfacher und ist sogar noch schneller.
int anzahl(const char * sb, const char * str)
{
std::string text(str);
std::string::size_type stelle = text.find(sb);
int result = 0;
while(stelle != std::string::npos)
{
result++;
stelle = text.find(sb, stelle+1);
}
return result;
}
-
mhhh, wenn dein lehrer sagt du sollst es in C schreiben und die Stringfunktionen (bzw. STL) nicht nehmen sollst, ist die Lösung sicherlich falsch.
-
HansGeorg schrieb:
naja wir haben es so gelernt, ich kann nichts dafür. unser lehrer hat halt gesagt das wir angeblich c lernen, aber das wir dann gleich mit cout beginnen hat mich auch gewundert, da es doch c++ ist.
ich sag's doch immer wieder: Was für Idioten gibt es, die sich Lehrer oder Prof. nennen 
@Hans: Wenn du eine Lösung in C brauchst, dann guck dir folgende Funktion an: man: strstr(3).
-
wieso glaub ich nicht, dass die lösung von dir ist
-
HansGeorg schrieb:
1 function NaiveSuche(string s[1..n], string sub[1..m])
2 for i from 1 to n
3 for j from 1 to m
4 if s[i+j-1] ≠ sub[j]
5 springe zur nächsten Iteration der äußeren Schleife
6 return i
7 return nicht gefundenNa das ist doch schon mal ein Lösungsansatz - den in C umzusetzen sollte doch nicht das Problem sein. Für die aktuelle Aufgabe mußt du nur Zeile 6 ersetzen durch "erhöhe Zähler und springe zur nächsten Iteration der äußeren Schleife".
Btw, die äußere Schleife muß nur bis n-m laufen, sonst rennst du über das Speicherende hinaus.
@supertux: Das hatte ich auch schon vorgeschlagen, ist aber anscheinend nicht zugelassen.