WICHTIG: Der Betrieb von goMatlab.de wird privat finanziert fortgesetzt. - Mehr Infos...

Mein MATLAB Forum - goMatlab.de

Mein MATLAB Forum

  
Gast > Registrieren       Autologin?   

Partner:




Forum
      Option
[Erweitert]
  • Diese Seite per Mail weiterempfehlen
     


Gehe zu:  
Neues Thema eröffnen Neue Antwort erstellen

kleinsten gemeinsamen substring finden
 

testuser

Gast

Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 12.09.2012, 10:58     Titel: kleinsten gemeinsamen substring finden
  Antworten mit Zitat      
Hallo,

ich habe eine Reihe von strings die einen unbestimmten gemeinsame substring enthalten. Wie kann ich diesen finden?

Bsp.:
Code:
s1='stringname';
s2='stringbeispiel';
s3='stringtest';

gesucht ist 'string'

Die länge des kleinsten gemeinsamen strings kenne ich natürlich nicht.

Ich hab schon ein bisschen mit den strcmp-Varianten rumprobiert, bin allerdings auf kein sinnvolles Ergebnis gekommen. Für hilfreiche Tips bin ich wie immer dankbar.

Grüße Gast


flashpixx
Forum-Guru

Forum-Guru

Beiträge: 355
Anmeldedatum: 19.04.08
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 12.09.2012, 12:23     Titel:
  Antworten mit Zitat      
Du wirst mit Standard String Funktionen da wohl keine Lösung finden, denn wenn Du die Länge nicht kennst, dann musst Du alle Teilstring suchen.

Dir wird da nur ein http://de.wikipedia.org/wiki/Suffixbaum helfen
Private Nachricht senden Benutzer-Profile anzeigen
 
Jan S
Moderator

Moderator

Beiträge: 11.057
Anmeldedatum: 08.07.10
Wohnort: Heidelberg
Version: 2009a, 2016b
     Beitrag Verfasst am: 12.09.2012, 13:03     Titel: Re: kleinsten gemeinsamen substring finden
  Antworten mit Zitat      
Hallo,

Beginnen die gleichen Substrings alle am Anfang der Strings?
Was soll geschehen, wenn mehrere Substrings die gleiche Länge haben?

Gruß, Jan
Private Nachricht senden Benutzer-Profile anzeigen
 
testuser

Gast

Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 12.09.2012, 13:39     Titel:
  Antworten mit Zitat      
Hallo, vereinfacht beginnen alle substrings am Anfang. Wenn der substring auch irgendwo innerhalb der strings liegt wäre das noch besser. Nichts soll passieren, ich will nur den substring haben, welcher in allen strings enthalten ist.
 
testuser

Gast

Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 13.09.2012, 13:26     Titel:
  Antworten mit Zitat      
Hallo,

ich hab jetzt noch ein bisschen probiert und eine sehr umständliche Lösung gefunden.

Code:
s = {'stringtest' 'stringname' 'strinwerweuißwas'};

smin=NaN;

for i=1:length(s)
smin = min(smin,length(s{i}));
end

weiter = true;

for i = 1:smin
    a = strncmp(s, s{1}, (smin - i));
    if (sum(a) == length(a)) && weiter
        itemp = smin - i;
        weiter = false;
    end
end

string = s{1}(1:itemp);


Für Alternativvorschläge bin ich nach wie vor dankbar.

Grüße testuser
 
Jan S
Moderator

Moderator

Beiträge: 11.057
Anmeldedatum: 08.07.10
Wohnort: Heidelberg
Version: 2009a, 2016b
     Beitrag Verfasst am: 13.09.2012, 17:09     Titel:
  Antworten mit Zitat      
Hallo testuser,

Code:
s = {'stringtest' 'stringname' 'strinwerweuißwas'};
c = double(char(s));   % double() ist eventuell unnötig
d = all(diff(c, 1, 1), 1);
len = find(d, 1);
string = s{1}(1:len - 1);

Oder:
Code:
s = {'stringtest' 'stringname' 'strinwerweuißwas'};
c = char(s);
d = all(bsxfun(@eq, c, c(1, :)), 1);
len = find(d, 1);
string = s{1}(1:len - 1);

Gruß, Jan
Private Nachricht senden Benutzer-Profile anzeigen
 
testuser

Gast

Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 14.09.2012, 10:01     Titel:
  Antworten mit Zitat      
Hallo Jan,

danke für den Tip, die erste Variante funktioniert nicht ganz so gut aber aus der zweiten ließ sich was machen.

Code:
s = {'stringtest' 'stringname' 'stringwerweuißwas'};
c = char(s);
d = all(bsxfun(@eq, c, c(1, :)), 1);
len = length(find(d));
string = s{1}(1:len);  


So klappt es ganz gut und ist deutlich übersichtlicher als meine Variante. Wenn du jetzt noch nen Tip hast wie man den längsten zusammenhängenden Substring innerhalb des Srings findet.
Eventuell in dieser Form:
Code:
s = {'11stringtest' '12stringname' '13stringwerweuißwas'};
 
Jan S
Moderator

Moderator

Beiträge: 11.057
Anmeldedatum: 08.07.10
Wohnort: Heidelberg
Version: 2009a, 2016b
     Beitrag Verfasst am: 14.09.2012, 11:01     Titel:
  Antworten mit Zitat      
Hallo,

Code:

Das ist tückisch, denn es zählt auf gleiche Buchstaben mit, die später auftauchen:
Code:
s = {'abc', 'adc', 'aec'};
d = all(bsxfun(@eq, c, c(1, :)), 1);
len = length(find(d));
% ==> 2!

Besser und eine Verbesserung meines Vorschlages:
Code:
len = find(d == 0, 1);

Also: Find den ersten Buchstaben, der nicht für alle Strings gleich ist.

Den längsten zusammenhängenden Substring zu finden ist deutlich schieriger. Welches Ergebnis erwartest Du für:
Code:
s1 = {'ab', 'ba'}
s2 = {'*ab*cd', '#ab#cd'}

Müssen die gleichen Buchstaben auch an der gleichen Position im String stehen?

Bringt Dich der Link von flashpixx weiter? Ein Kommentar dazu wäre hilfreich.

Gruß, Jan
Private Nachricht senden Benutzer-Profile anzeigen
 
testuser

Gast

Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 14.09.2012, 11:30     Titel:
  Antworten mit Zitat      
Hey,

der Link hilft nicht wirklich, zumindest hab ich keine Ahnung wie ich sowas umsetzen sollte.
Der gemeinsame Substring wird sehr wahrscheinlich immer an der gleichen Stelle im String beginnen.
Wenn man in
Code:
s={'11stringtest' '12stringname' '13stringwerweuißwas'};

Code:
findet wäre das schon eine große Hilfe.

Grüße testuser
 
Neues Thema eröffnen Neue Antwort erstellen



Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:

 Du kannst Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
Du kannst Dateien in diesem Forum posten
Du kannst Dateien in diesem Forum herunterladen
.





 Impressum  | Nutzungsbedingungen  | Datenschutz | FAQ | goMatlab RSS Button RSS

Hosted by:


Copyright © 2007 - 2025 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks

MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.