[C] Funktion zum Suchen schreiben [eilt, da für Schule]

[HansGeorg]

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.

zu den stringfunktionen, diese zwei dürfen wir benutzen aber nicht mehr. ohne diese funktionen würde es auch zu umfangreich sein.

zu der speicherreservierung. hoppla, da hat sich wohl ein kleiner fehler eingeschlichen.

[CStoll]

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.

*verd - wo ist der Kopf-durch-die-Wand Smilie?*

zu den stringfunktionen, diese zwei dürfen wir benutzen aber nicht mehr. ohne diese funktionen würde es auch zu umfangreich sein.

Ach, wo du schon dabei bist, kannst du die zwei Funktionen auch noch selber schreiben

// schnell hingeschrieben und nicht optimiert

int mystrlen(const char* str)
{
  int l=0;
  while(str[l]!='\0')++l;
  return l;
}

void mystrcpy(char* tgt,const char* src)
{
  for(int i=0;i<=mystrlen(src);++i)tgt[i]=src[i];
}

[HansGeorg]

aha danke für diese kleine hilfe. ja ich hab mich auch schon gefragt warum der lehrer alles vermischt und nichts trennt...

aber ich hab immer noch eine frage. wenn ich die strings dann zeichenweise verglichen habe (also die erste runde) und es ist identisch, wie speichere ich die anzahl dann ab in eine variable?

sorry für diese bescheurten fragen, aber unser lehrer ist nich im stande gut zu erklären.

hab mich deshalb selbst weitergebildet.

naja und diese funktion wird bewertet.

[CStoll]

Du nimmst dir eine int-Variable und initialisierst sie mit 0. Anschließend kannst du immer, wenn der Suchstring gefunden wurde, sie inkrementieren (++).

[HansGeorg]

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...

[Daniel E.]

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.

[ewo]

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.

[TheTester]

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-Algorithmus

Dabei handelt es sich um drei der bekanntesten Algorithmen.

tt

[HansGeorg]

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 gefunden

jedoch kann ich mit der sprache nicht so viel anfangen, wie schreib ich das für CPP um?

[HansGeorg]

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;
}

[Rontha]

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.

[supertux]

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).

[ewo]

wieso glaub ich nicht, dass die lösung von dir ist

[CStoll]

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 gefunden

Na 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.