Alogrithmus der Palindrome herausfindet?

[*-_JuLi²_-*]

Hey Leute, ich hab mal eine kleine Frage an euch. Undzwar brauche ich ein Programm das aus einer Textdatei so schnell wie möglich die Anzahl der Palindrome (=Wörter die rückwärts gelesen das gleiche sind (anna, lol,...)) herausfindet und ausgibt. Klein-Großbuchstaben müssen beachtet werden (Anna gilt in dem Fall nicht, anna schon).
Ich brauch eigentlich nur den Alogrithmus, der schnellere bekommt meine 8e*g. :b

[th0rex]

#include <iostream>
#include <string>

inline bool is_palindrome(const std::string& in)
{
	std::string reverse(in.rbegin(), in.rend());
	return reverse == in;
}

int main(int, char**)
{
	std::string a = "anna";
	std::string b = "Anna";
	std::cout << is_palindrome(a);
	std::cout << is_palindrome(b);
}

Gibt 1 und dann 0 aus (true, false). Da könnte man schon drauf kommen ...

Edit: Das ist c++ und von c der c standart library habe ich nicht viel Ahnung. Und um das zählen zu können musst du wissen, ob es eins ist.

[*-_JuLi²_-*]

Originally Posted by omitma

#include <iostream>
#include <string>

inline bool is_palindrome(const std::string& in)
{
	std::string reverse(in.rbegin(), in.rend());
	return reverse == in;
}

int main(int, char**)
{
	std::string a = "anna";
	std::string b = "Anna";
	std::cout << is_palindrome(a);
	std::cout << is_palindrome(b);
}

Gibt 1 und dann 0 aus (true, false). Da könnte man schon drauf kommen ...

Ist das C++? Vergessen zu sagen, nur C bitte und eher für anfänger :b

Ich brauche keinen algorithmus der mir ausgibt ob es ein Palindrom ist oder nicht sondern eins das zählt wieviele in dem Textdokument sind.

[Dr. Coxxy]

bool IsPalindrom(char* a, size_t Length)
{
	for (char* Temp = a + Length - 1; Temp >= a; Temp--, a++)
	{
		if (*a != *Temp)
		{
			return false;
		}
	}
	return true;
}

void PrintPalindromesInText(char* Text)
{
	int Found = 0;
	
	while (*Text != '\0')
	{
		size_t TempLen = 0;
		char* Temp = Text;
		while (isalpha(*Temp))
		{
			*Temp++;
			TempLen++;
		}
		if (IsPalindrom(Text, TempLen))
		{
			puts("Found: ");
			for (size_t i = 0; i < TempLen; i++)
			{
				putchar(Text[i]);
			}
			putchar('\n');
			Found++;
		}
		Text += TempLen+1;
	}

	printf("Found %d Palindromes!\n", Found);
}

//aufzurufen z.b.:
PrintPalindromesInText("huhu test anna qwer alla butter reger abba cdddc");

kann man mit strtok noch verkürzen wenn man alle delimiter kennt, ich habs jetzt umgekehrt gemacht und nur das alphabet als gültige zeichen zugelassen.

EDIT:
hier die strtok version:

void PrintPalindromesInText(char* Text)
{
	int Found = 0;

	char* Buffer = new char[strlen(Text) + 1];
	strcpy(Buffer, Text);
	const char* Seperators = " ,.!?;\t\n";

	char* Token = strtok(Buffer, Seperators);
	
	while (Token)
	{
		if (IsPalindrom(Token, strlen(Token)))
		{
			printf("Found: %s\n", Token);
			Found++;
		}
		Token = strtok(NULL, Seperators);
	}

	printf("Found %d Palindromes!\n", Found);
}

anwendung genauso wie oben.

den string neu zu kopieren kann man sich sparen wenn man den text vorher in nem veränderbaren buffer hat und nicht als const string übergibt.

[*-_JuLi²_-*]

Originally Posted by Dr. Coxxy

bool IsPalindrom(char* a, size_t Length)
{
	for (char* Temp = a + Length - 1; Temp >= a; Temp--, a++)
	{
		if (*a != *Temp)
		{
			return false;
		}
	}
	return true;
}

void PrintPalindromesInText(char* Text)
{
	int Found = 0;
	
	while (*Text != '\0')
	{
		size_t TempLen = 0;
		char* Temp = Text;
		while (isalpha(*Temp))
		{
			*Temp++;
			TempLen++;
		}
		if (IsPalindrom(Text, TempLen))
		{
			puts("Found: ");
			for (size_t i = 0; i < TempLen; i++)
			{
				putchar(Text[i]);
			}
			putchar('\n');
			Found++;
		}
		Text += TempLen+1;
	}

	printf("Found %d Palindromes!\n", Found);
}

//aufzurufen z.b.:
PrintPalindromesInText("huhu test anna qwer alla butter reger abba cdddc");

kann man mit strtok noch verkürzen wenn man alle delimiter kennt, ich habs jetzt umgekehrt gemacht und nur das alphabet als gültige zeichen zugelassen.

EDIT:
hier die strtok version:

void PrintPalindromesInText(char* Text)
{
	int Found = 0;

	char* Buffer = new char[strlen(Text) + 1];
	strcpy(Buffer, Text);
	const char* Seperators = " ,.!?;\t\n";

	char* Token = strtok(Buffer, Seperators);
	
	while (Token)
	{
		if (IsPalindrom(Token, strlen(Token)))
		{
			printf("Found: %s\n", Token);
			Found++;
		}
		Token = strtok(NULL, Seperators);
	}

	printf("Found %d Palindromes!\n", Found);
}

anwendung genauso wie oben.

den string neu zu kopieren kann man sich sparen wenn man den text vorher in nem veränderbaren buffer hat und nicht als const string übergibt.

Also erstmal Danke dafür, jedoch muss ich das aus einer Textdatei ausführen (mit fopen undso) und da muss ich mit Arrays arbeiten um die Wörter aus der Textdatei herauszufiltern.

[Dr. Coxxy]

Originally Posted by *-_JuLi²_-*

Also erstmal Danke dafür, jedoch muss ich das aus einer Textdatei ausführen (mit fopen undso) und da muss ich mit Arrays arbeiten um die Wörter aus der Textdatei herauszufiltern.

du wirst es doch wohl hinkriegen den text aus der textdatei in ein char array zu laden und das dann PrintPalindromesInText zu übergeben, oder?
um festzustellen ob ein wort ein palindrom ist kannst du meine IsPalindrom benutzen, um den gesamttext in einzelne wörter zu unterteilen wie in PrintPalindromesInText gezeigt strtok benutzen.

[*-_JuLi²_-*]

Originally Posted by Dr. Coxxy

du wirst es doch wohl hinkriegen den text aus der textdatei in ein char array zu laden und das dann PrintPalindromesInText zu übergeben, oder?
um festzustellen ob ein wort ein palindrom ist kannst du meine IsPalindrom benutzen, um den gesamttext in einzelne wörter zu unterteilen wie in PrintPalindromesInText gezeigt strtok benutzen.

Ich hab bei meinem Algo das bis jetzt immer Wort für Wort gemacht und das ist so ziemlich das gleiche wie dein IsPalindrom, wenn ich mich nicht irre.

Ich brauch jedoch einen der das so schnell wie möglich macht, oder ist das so ziemlich das schnellste? In meiner Mainfunktion zählt der so lange bis er zu einem Leerzeichen kommt und geht dann ins IsPalindrom, wenn er das überprüft hat geht er wieder in die Hauptfunktion und macht so weiter.
Es geht bei diesem Programm um die schnelligkeit, geht das nicht irgendwie noch schneller?

[MrSm!th]

Du willst also einfach eine copy&paste fertige Lösung? Dann bist du hier falsch.

[*-_JuLi²_-*]

Originally Posted by MrSm!th

Du willst also einfach eine copy&paste fertige Lösung? Dann bist du hier falsch.

Nein, ich brauch einen möglichst schnellen Algorithmus der mir aus meiner Textdatei die Anzahl der Palindrome ausliest. Bin noch Anfänger.

[Schlüsselbein]

Und warum brauchst du das?

[*-_JuLi²_-*]

Originally Posted by Schlüsselbein

Und warum brauchst du das?

Rein aus Test bzw Lernzwecken. Da ich, wie gesagt, noch Anfänger bin und ich C lernen möchte hab ich mich heute mal rangesetzt und versucht einen möglichst schnellen Algorithmus für das herauszufinden. Ich suche lediglich einen schnelleren als meinen.

Hier mal mein Code:

while((text[i] = fgetc(fp)) != EOF)
	{
		if(text[i] == 32) 
		{
			if(palindrom(i,text) == 1)
			{
				zähler++;
			}
			i = -1;
		}
		i++;
	}

int palindrom(int i, char text[])
{
	int z = 0;
	i--;
	while(z <= i)
	{
		if(text[z] != text[i])
		{
			return 0;
		}
		i--;
		z++;
	}
	return 1;
}

[Schlüsselbein]

Wenn du die Algorithmen vergleichen möchtest, solltest du den Text davor einlesen und dann messen - falls es die Größe der Datei zulässt.

[*-_JuLi²_-*]

Originally Posted by Schlüsselbein

Wenn du die Algorithmen vergleichen möchtest, solltest du den Text davor einlesen und dann messen - falls es die Größe der Datei zulässt.

Eben nicht, ich hab mir eine fast 10MB große Textdatei erstellt mit Palindromen und normale Wörter. Ich messe die Zeit übrigens mit der clock() funktion.

[Schlüsselbein]

Eine 10MB Datei wird bei mir im Bruchteil einer Sekunde eingelesen - von einer 0815 Festplatte, nicht von meiner SSD.
Also lese die Werte ein und zähle anschließend die Palindrome. Somit solltest du unverfälschte Ergebnisse bekommen.

Außerdem kein Zitat nötig, wenn du auf den Post über dir antwortest.

[*-_JuLi²_-*]

Einlesen kann ich das auch aber wie kann ich 10MB Text in ein Array speichern?