Sachverhalt:
Sachverhalt:
A. A._ (Kläger) war seit dem 1. Januar 1993 als Filialleiter der B._ AG (Beklagte) im C._-Shopping angestellt, wo Videos, DVDs und Computerspiele zum Kauf angeboten wurden. Er wurde an seinen freien Tagen durch D._ vertreten, die in der Filiale als Aushilfsverkäuferin tätig war. Anfangs Dezember 2001 meldete D._ der Verkaufsleitung der Beklagten verschiedene von ihr festgestellte Ungereimtheiten. Diese erweckten den Verdacht, der Kläger habe Artikel aus dem Sortiment gestohlen bzw. veruntreut. Die Beklagte erstattete deshalb am 10. Dezember 2001 Strafanzeige gegen den Kläger. Nachdem die Staatsanwaltschaft Basel-Stadt die Vorgesetzten des Klägers und D._ einvernommen hatte, liess sie den Kläger am 22. Januar 2002 polizeilich zur Einvernahme vorführen und durchsuchte gleichzeitig seine Wohnung. Dort wurde allerdings nichts beschlagnahmt.
Am 23. Januar 2002 kündigte die Beklagte das Arbeitsverhältnis mit dem Kläger per 30. April 2002. Da der Kläger indessen seit diesem Tag krank geschrieben war, erwies sich diese Kündigung als nichtig. Nach Ablauf der gesetzlichen Sperrfrist von 180 Tagen kündigte die Beklagte dem Kläger mit Schreiben vom 25. Juli 2002 erneut auf den 31. Oktober 2002.
Das Strafverfahren gegen den Kläger wurde nach weiteren Ermittlungen mit Beschluss der Staatsanwaltschaft vom 27. August 2002 eingestellt, da kein hinreichender Beweis des Tatbestandes bzw. keine rechtsgültigen Strafanträge für allfällige geringfügige Vermögensdelikte vorlagen.
Das Strafverfahren gegen den Kläger wurde nach weiteren Ermittlungen mit Beschluss der Staatsanwaltschaft vom 27. August 2002 eingestellt, da kein hinreichender Beweis des Tatbestandes bzw. keine rechtsgültigen Strafanträge für allfällige geringfügige Vermögensdelikte vorlagen.
B. Am 11. Februar 2003 klagte A._ beim Gewerblichen Schiedsgericht Basel-Stadt gegen die Beklagte auf Zahlung von sechs Bruttomonatslöhnen, d.h. Fr. 27'618.--, zuzüglich Zins als Entschädigung für missbräuchliche Kündigung. Mit Urteil vom 18. August 2003 wies das Gewerbliche Schiedsgericht die Klage ab. Eine gegen dieses Urteil gerichtete Beschwerde des Klägers wies der Ausschuss des Appellationsgerichts des Kantons Basel-Stadt am 13. Januar 2004 ab.
B. Am 11. Februar 2003 klagte A._ beim Gewerblichen Schiedsgericht Basel-Stadt gegen die Beklagte auf Zahlung von sechs Bruttomonatslöhnen, d.h. Fr. 27'618.--, zuzüglich Zins als Entschädigung für missbräuchliche Kündigung. Mit Urteil vom 18. August 2003 wies das Gewerbliche Schiedsgericht die Klage ab. Eine gegen dieses Urteil gerichtete Beschwerde des Klägers wies der Ausschuss des Appellationsgerichts des Kantons Basel-Stadt am 13. Januar 2004 ab.
C. Der Kläger führt gegen das Urteil des Appellationsgerichts eidgenössische Berufung. Er beantragt die Aufhebung des angefochtenen Urteils und die Gutheissung der Klage. Die Beklagte schliesst auf Abweisung des Rechtsmittels.

Das Bundesgericht zieht in Erwägung:
Das Bundesgericht zieht in Erwägung:
1. Die kantonalen Instanzen sind zum Schluss gekommen, es liege keine missbräuchliche Kündigung vor. Es sei keiner der in Art. 336 OR aufgeführten Tatbestände erfüllt. Die Gründe, die zur Kündigung geführt hätten, könnten auch nicht den vom Gesetz ausdrücklich missbilligten gleichgesetzt werden. Für die Kündigung sei der objektive Vertrauensverlust entscheidend gewesen, nicht die Krankheit des Arbeitnehmers. Mit Blick auf die langjährige Dauer des Arbeitsverhältnisses wäre zwar ein etwas schonenderes Vorgehen der Beklagten denkbar gewesen; insbesondere wäre es durchaus nicht abwegig gewesen, wenn sie den Kläger nach dessen Einvernahme bei der Staatsanwaltschaft angehört hätte, bevor sie die Kündigung aussprach. Es könne ihr aber nicht vorgeworfen werden, das Gebot der schonenden Rechtsausübung in krasser Weise verletzt zu haben, so dass ihr Verhalten als rechtsmissbräuchlich bezeichnet werden müsste.
Der Kläger sieht darin eine falsche Anwendung von Art. 336 OR und Art. 2 Abs. 2 ZGB. Er macht somit eine Bundesrechtsverletzung geltend (Art. 43 Abs. 1 OG), und auf die Berufung ist, da auch die übrigen Zulässigkeitsvoraussetzungen erfüllt sind, grundsätzlich einzutreten.
Der Kläger sieht darin eine falsche Anwendung von Art. 336 OR und Art. 2 Abs. 2 ZGB. Er macht somit eine Bundesrechtsverletzung geltend (Art. 43 Abs. 1 OG), und auf die Berufung ist, da auch die übrigen Zulässigkeitsvoraussetzungen erfüllt sind, grundsätzlich einzutreten.
2. 2.1 Für die Rechtmässigkeit einer Kündigung bedarf es grundsätzlich keiner besonderen Gründe, da das schweizerische Arbeitsrecht auch nach der Revision von 1988 vom Prinzip der Kündigungsfreiheit ausgeht (vgl. <ref-ruling> E. 2a). Missbräuchlich ist eine Kündigung grundsätzlich nur, wenn sie aus bestimmten unzulässigen Gründen ausgesprochen wird, die in Art. 336 OR umschrieben werden. Die Aufzählung in Art. 336 OR ist allerdings nicht abschliessend. Sie konkretisiert vielmehr das allgemeine Rechtsmissbrauchsverbot und gestaltet dieses mit für den Arbeitsvertrag geeigneten Rechtsfolgen aus. Es sind deshalb weitere Tatbestände ohne weiteres denkbar und vom Bundesgericht auch schon mehrfach anerkannt worden (vgl. zum Ganzen <ref-ruling> E. 2a S. 72 mit zahlreichen Hinweisen; ferner <ref-ruling> E. 3b S. 251; <ref-ruling> E. 3b S. 61 f.). Diese müssen aber eine vergleichbare Schwere aufweisen, wie die in Art. 336 OR ausdrücklich aufgeführten.
Der Missbrauch einer Kündigung kann sich nicht nur aus den Kündigungsmotiven sondern auch aus der Art und Weise ergeben, wie die kündigende Partei ihr Recht ausübt (<ref-ruling> E. 4b/bb S. 166; bestätigt in <ref-ruling> E. 2b). Selbst wenn eine Partei die Kündigung rechtmässig erklärt, muss sie das Gebot schonender Rechtsausübung beachten. Sie darf insbesondere kein falsches und verdecktes Spiel treiben, das Treu und Glauben krass widerspricht (<ref-ruling> E. 2b; <ref-ruling> E. 4b/cc S. 167). Ein krass vertragswidriges Verhalten, namentlich eine schwere Persönlichkeitsverletzung im Umfeld einer Kündigung, kann diese als missbräuchlich erscheinen lassen. Demgegenüber genügt ein bloss unanständiges, einem geordneten Geschäftsverkehr unwürdiges Verhalten nicht. Es ist nicht Aufgabe der Rechtsordnung, bloss unanständiges Verhalten zu sanktionieren.
2.2 Der Kläger macht zunächst geltend, die Kündigung sei missbräuchlich, weil sie wegen seiner Erkrankung erfolgt sei.
2.2.1 Die Vorinstanz hat in tatsächlicher Hinsicht verbindlich (Art. 63 Abs. 2 OG) festgehalten, dass die Kündigung in keinem kausalen Verhältnis zur Krankheit stand. Diese sei bei der wirksamen, zweiten Kündigung nur deshalb erwähnt worden, um festzuhalten, dass der krankheitsbedingte zeitliche Kündigungsschutz nun abgelaufen sei. Soweit der Kläger seinen Vorwurf der Missbräuchlichkeit mit der Kündigung wegen Krankheit begründet, geht er somit von einem Sachverhalt aus, der im angefochtenen Urteil keine Stütze findet. Da er in diesem Zusammenhang bloss frei gehaltene Kritik an der Beweiswürdigung der Vorinstanz übt, jedoch keine Ausnahme im Sinne von Art. 63 Abs. 2 und Art. 64 OG anruft, die dem Bundesgericht eine Überprüfung der tatsächlichen Feststellungen des Sachgerichts erlaubt, kann auf die Berufung insoweit nicht eingetreten werden (vgl. <ref-ruling> E. 2.2; <ref-ruling> E. 2c; <ref-ruling> E. 1e S. 205).
2.2.2 Auch bei materieller Beurteilung wäre dem Standpunkt des Klägers nicht zu folgen, selbst wenn seine Krankheit die Arbeitsfähigkeit vermindert hat, wovon nach dem angefochtenen Urteil auszugehen ist. Eine Krankheit ist eine persönliche Eigenschaft, die gemäss Art. 336 Abs. 1 lit. a OR für den Kündigungsschutz relevant sein kann. Zu beachten ist indessen, dass der sachliche Kündigungsschutz entfällt, wenn die persönliche Eigenschaft die Arbeitsfähigkeit beeinträchtigt. Insofern schränkt Art. 336 Abs. 1 lit. a OR den Persönlichkeitsschutz ein. Die Kündigung wegen Krankheit hat zur Folge, dass für die Zukunft die Lohnfortzahlungspflicht entfällt, wenn die Krankheit zur Arbeitsunfähigkeit führt. Insofern könnte es sich bei einer Kündigung wegen einer Krankheit um eine Vereitelungskündigung im Sinn von Art. 336 Abs. 1 lit. c OR handeln. Aufgrund der Systematik des gesamten Kündigungsschutzes ist indessen anzunehmen, dass der Gesetzgeber nicht soweit gehen wollte. Daher scheint es zulässig, nach Ablauf des zeitlichen Kündigungsschutzes jemandem wegen einer die Arbeitsleistung beeinträchtigenden Krankheit zu kündigen (<ref-ruling> E. 5 mit Hinweisen).
2.3 Der Kläger hält weiter dafür, die von der Beklagten gegen ihn eingereichte Strafanzeige, die polizeiliche Vorführung und die Hausdurchsuchung seien ein unverhältnismässiges und unnötig verletzendes Vorgehen gewesen. Die Beklagte habe es an einer schonenden Rechtsausübung missen lassen. Ihr Vorgehen stelle ein rechtsmissbräuchliches Verhalten dar, was zur Missbräuchlichkeit der Kündigung im Sinne von Art. 336 OR führe.
2.3.1 Der Kläger widerspricht in diesem Zusammenhang der tatsächlichen Feststellung der Vorinstanz, wonach die Beobachtungen der Aushilfsverkäuferin und weitere Indizien bei der Beklagten den schwerwiegenden Verdacht erweckt hätten, dass der Kläger deliktische Handlungen zu ihrem Nachteil begangen haben könnte. Ferner macht er in Erweiterung des von der Vorinstanz festgestellten Sachverhalts geltend, die Beklagte habe mit ihrem Vorgehen wider besseres Wissen gehandelt, und er habe allen Grund zur Annahme, dass die Beklagte ihn im Hinblick auf die Schliessung ihrer Filialen in Basel unter irgend einem Vorwand habe los werden wollen. Da er sich auch in diesem Zusammenhang nicht auf eine Ausnahme von der Bindung an die vorinstanzlichen Sachverhaltsfeststellungen nach Art. 63 Abs. 2 und Art. 64 OG beruft, kann er insoweit nicht gehört werden (vgl. Erwägung 2.2.1 vorne).
2.3.2 Der Kläger sieht sich in seinem Standpunkt, die Beklagte habe das Gebot einer schonenden Rechtsausübung krass verletzt, durch <ref-ruling> E. 4b/cc S. 166 f. bestätigt. Er übersieht indessen, dass sich der Sachverhalt im zitierten Entscheid von dem hier zu beurteilenden in wesentlichen Punkten unterscheidet.
Im zitierten Entscheid hatte die Franchisegeberin in der Folge von gewissen Meinungsverschiedenheiten mit der Franchisenehmerin über die Erhöhung der Nutzungsgebühren bereits einen Vertrag mit einer anderen Person für die Übernahme des Geschäftes geschlossen, ohne dass die Franchisenehmerin davon etwas zu wissen bekam. Über zwei Monate später beruhigte sie die Franchisenehmerin noch mit dem Hinweis, sie habe bezüglich der Nutzungsgebühren noch nichts entschieden. Sie täuschte somit während mehreren Monaten vor, das Vertragsverhältnis fortführen zu wollen, obgleich sie sich bereits entschieden hatte, dieses zu beenden. Erst kurzfristig vor dem Zeitpunkt, auf den die neue Arbeitskraft angestellt worden war, hatte sie sodann ihren Standpunkt der bisherigen Franchisenehmerin bekannt gegeben, um dann deren Weigerung, die Gebührenerhöhung zu akzeptieren, zur kurzfristigen Auflösung des Vertragsverhältnisses zu verwenden. Das Bundesgericht hat bei diesem Sachverhalt die Ansicht der Vorinstanz geteilt, die Franchisegeberin habe ein falsches und verstecktes Spiel getrieben und krass gegen Treu und Glauben verstossen. Sie hatte in krasser Weise dem Gebot der schonenden Rechtsausübung zuwidergehandelt und sich widersprüchlich verhalten (<ref-ruling> E. 4b/cc S. 167).
Vorliegend lässt sich der Beklagten hingegen keinerlei widersprüchliches Verhalten vorhalten. Sie hat gegenüber dem Kläger nie zum Ausdruck gebracht, sie wolle das Arbeitsverhältnis mit ihm weiterführen, nachdem sie sich zur Kündigung bereits entschlossen hatte. Dass sie dem Kläger die Verdächtigungen nicht sofort mitteilte, ergab sich - wie die kantonalen Instanzen feststellten - zwingend aus den Bedürfnissen der polizeilichen Abklärungen. Dem von der Vorinstanz festgestellten, massgeblichen Sachverhalt, ist überdies in keiner Weise zu entnehmen, dass die Arbeitgeberin sich bereits vor den polizeilichen Massnahmen zu einer Kündigung entschlossen hätte.
Das konkrete Vorgehen der staatlichen Behörden lag zudem nicht im Einflussbereich der Arbeitgeberin. Dieses haben vielmehr die Behörden selber zu verantworten. Ob dieses Vorgehen mit Blick auf die vorgebrachten Vorwürfe und den damaligen Wissensstand der Arbeitgeberin und der Untersuchungsbehörden verhältnismässig war oder nicht, braucht deshalb vorliegend nicht beurteilt zu werden. Angesichts der erhobenen Vorwürfe kann die Strafanzeige selber nicht als unverhältnismässig bezeichnet werden. Ob auch andere Wege, wie beispielsweise eine private Überwachung möglich und der Arbeitgeberin zumutbar gewesen wären, ist nicht dargetan. Von einer rechtsmissbräuchlichen Rechtsausübung kann somit nicht gesprochen werden.
2.4 Schliesslich sieht der Kläger eine Rechtsmissbräuchlichkeit auch darin, dass die Beklagte die Kündigung aussprach, ohne vorgängig mit ihm das Gespräch zu suchen.
Es ist ihm zuzugestehen, dass dieses Vorgehen wenig verständlich ist. Einem gesitteten Vorgehen im Geschäftsverkehr entspricht es grundsätzlich, das Gespräch mit der Gegenpartei zu suchen, bevor Schritte ergriffen werden, die für die andere Partei dramatische Folgen haben können. Es ist aber zwischen einem unanständigen und einem rechtswidrigen Verhalten zu unterscheiden. Es ist nicht Aufgabe der Rechtsordnung jedes Fehlverhalten zu sanktionieren. Nur Verstösse gegen gesellschaftliche Verhaltensnormen, die so krass sind, dass sie von der Gesellschaft nicht toleriert werden können, muss die Rechtsordnung durch geeignete Massnahmen unterbinden. Das schweizerische Arbeitsvertragsrecht sieht eine Anhörungspflicht vor der Kündigung nun aber gerade nicht vor. Wohl besteht ein Anspruch auf Begründung einer Kündigung (Art. 335 Abs. 2 OR). Diese muss aber erst im Nachhinein erfolgen. Wäre eine vorhergehende Anhörung zwingend, müssten sinnvoller Weise bereits bei einer solchen auch die Kündigungsgründe offen gelegt werden. Soweit wollte der Gesetzgeber indessen nicht gehen (vgl. dazu BGE <ref-ruling> E. 3b; vgl. ferner Brühwiler, Kommentar zum Einzelarbeitsvertrag, 2. Aufl., Bern/Stuttgart/Wien 1996, N. 8 zu Art. 335 OR und Streiff/von Kaenel, Arbeitsvertrag, 5. Aufl., Zürich 1992, N. 13 zu Art. 335 OR, die gar nur einen Anspruch auf schriftliche, nicht aber auf mündliche Begründung der Kündigung anerkennen; insoweit a.M. Rehbinder, Berner Kommentar, N. 9 zu Art. 335 OR; Brunner/Bühler/Waeber, Kommentar zum Arbeitsvertragsrecht, 2. Aufl., Basel 1997, N. 20 zu Art. 335 OR; Duc/Subilia, Commentaire du contrat individuel de travail, Lausanne 1998, N. 18 zu Art. 335 OR). Es geht nicht an, diesen gesetzgeberischen Entscheid über den Umweg von Art. 2 Abs. 2 ZGB umzustossen und einen rechtlichen Anspruch auf vorgängige Anhörung einzuführen. Auch insoweit ist der Vorinstanz zuzustimmen, wenn sie das Vorliegen einer Missbräuchlichkeit der Kündigung verneint.
2.5 Es ginge nun allerdings fehl, alle Vorwürfe nur einzeln zu betrachten. Die Beantwortung der Frage, ob eine Kündigung missbräuchlich ist, setzt richtiger Weise eine Gesamtwürdigung voraus.
Die Beklagte muss sich vorwerfen lassen, dass es kaum als anständig bezeichnet werden kann, das Gespräch mit dem Kläger nicht einmal gesucht zu haben. Ob es nicht schonendere Möglichkeiten gegeben hätte, die erhobenen Vorwürfe abzuklären, ist offen. Die Kündigung traf den Kläger sicher in einer mit Blick auf seinen Gesundheitszustand schwierigen Situation. Von daher ist seine Verletzung und damit auch seine Verärgerung über das Vorgehen der Beklagten verständlich. Das reicht aber mit Blick auf das in der Schweiz geltende Prinzip der Kündigungsfreiheit nicht, um eine Missbräuchlichkeit der Kündigung anzunehmen. Der Berufung des Klägers kann deshalb kein Erfolg beschieden sein.
Die Beklagte muss sich vorwerfen lassen, dass es kaum als anständig bezeichnet werden kann, das Gespräch mit dem Kläger nicht einmal gesucht zu haben. Ob es nicht schonendere Möglichkeiten gegeben hätte, die erhobenen Vorwürfe abzuklären, ist offen. Die Kündigung traf den Kläger sicher in einer mit Blick auf seinen Gesundheitszustand schwierigen Situation. Von daher ist seine Verletzung und damit auch seine Verärgerung über das Vorgehen der Beklagten verständlich. Das reicht aber mit Blick auf das in der Schweiz geltende Prinzip der Kündigungsfreiheit nicht, um eine Missbräuchlichkeit der Kündigung anzunehmen. Der Berufung des Klägers kann deshalb kein Erfolg beschieden sein.
3. Die Berufung ist abzuweisen, soweit darauf eingetreten werden kann. Verfahrenskosten sind mit Blick auf den Streitwert keine zu erheben (Art. 343 Abs. 3 OR). Die obsiegende Partei hat auch in Verfahren, die nach Art. 343 Abs. 3 OR kostenlos sind, grundsätzlich Anspruch auf Ersatz der Parteikosten (<ref-ruling> E. 5c S. 42). Der Kläger hat demnach die anwaltlich vertretene Beklagte für das bundesgerichtliche Verfahren zu entschädigen (Art. 159 Abs. 2 OG).

Demnach erkennt das Bundesgericht:
Demnach erkennt das Bundesgericht:
1. Die Berufung wird abgewiesen, soweit darauf einzutreten ist.
1. Die Berufung wird abgewiesen, soweit darauf einzutreten ist.
2. Es wird keine Gerichtsgebühr erhoben.
2. Es wird keine Gerichtsgebühr erhoben.
3. Der Kläger hat die Beklagte für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
3. Der Kläger hat die Beklagte für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Ausschuss, schriftlich mitgeteilt.
Lausanne, 5. August 2004
Im Namen der I. Zivilabteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: