003
30.03.2007, 21:22 Uhr
Pablo
Supertux
(Operator)
|
Abgesehen davon, dass dein Agorithmus in O(n²) läuft (deine Implementierug sogar O(n^4)), ist deine Idee nicht schlecht, aber ... hier sind deine Fehler:
1.
| C++: |
sstring = malloc(sizeof(str2)+1);
|
es sollte sein
| C++: |
sstring = malloc(strlen(str2)+1);
|
sizeof liefert die Größe in Bytes, die str2 in Anspruch nimmt. Da str2 ein char* ist, bekommst du immer 4 (bei x68 Rechnern). Du willst aber die Länge der Zeichenkette, auf die str2 zeigt, also musst du strlen(3) nehmen.
2.
| C++: |
for (a=0; a<strlen(str1)-strlen(str2)+1; a++)
|
Gar nicht performant, denn bei jedem Schleifendruchlauf berechnest du die Länge von str1 und str2, also O(n). Es könnte aber deutlich schneller laufen, O(1), wenn du gemacht hättest
| C++: |
int len_str1, len_str2;
...
len_str1 = strlen(str1);
len_str2 = strlen(str2);
for (a=0; a<len_str1 - len_str2 +1; a++)
|
Du setzt auch im Voraus, dass len(str1) > len(str2) gilt. In deinem Fall passt, aber ist nicht allgemein gültig.
3.
| C++: |
for (b=0; b<strlen(str2); b++)
|
Siehe 2.
4.
| C++: |
/* sstring[b]=0; */
printf("%s\n", sstring); /* Kontrollausgabe */
|
Das war schon richtig, bis du es in /* ... */ gesteckt hast, sstring muss nul-terminiert sein, wenn du strcmp(3) nimmst. Außerdem hast du Glück, dass dein Programm nicht gleich beim printf abgeschmiert ist.
5.
| C++: |
if (strcmp(str1, sstring))
|
Erstens liefert strcmp eine 0 bei Übereinstimmung, etwas != 0 sonst.
Zweitens erwartet strcmp 2 nul-termnierende Zeichenketten, sstring ist es nicht.
Drittens strcmp vergleicht die Zeichenkette str1 mit sstring, ist logisch, dass strcmp nie 0 zurückliefert. Komisch, dass es nicht gleich beim ersten Schleifendruchlauf abbricht.
Was du hättest benutzen müssen: strncmp(3). strncmp vergleicht die ersten n Zeichen. Außerdem sollte es str2 heißen.
| C++: |
sstring[b]=0;
printf("%s\n", sstring); /* Kontrollausgabe */
if (!strncmp(str2, sstring, b))
{
printf("Übereinstimmung\n");
return a;
}
|
Zu Beefy's Lösung: strstr liefert einen Zeiger auf die Stelle, wo str2 in str1 vorkommt. Da der Speicher linear ist (damit meine ich, dass die Daten nicht fragmentiert sind), ist die Substraktion der Adresse der Überenstimmung und des Anfangs von str1 genau das Index, wo die Übereinstimmung stattfindet. Sprich, wenn str1 auf die Stelle n zeigt, und str2 stimmt auf Stelle n+k überein, dann liefert Beefy's funktion n + k - n = k.
6. Du machst nie
--
A! Elbereth Gilthoniel!
silivren penna míriel
o menel aglar elenath,
Gilthoniel, A! Elbereth!
Dieser Post wurde am 30.03.2007 um 21:30 Uhr von Pablo editiert. |
