✔ Suche nach Gemeinsamkeiten im endlichen Alphabet

[NTDY]

Beispielweise habe ich ein Alphabet von Buchstaben von a-g (a,b,c,d,e,f,g)
Und gegeben ist eine beliebige Anordung dieser Buchstaben, bspw.:

cegabedecegcgbacceffgecegcdcegabceg

Gefunden werden sollen nun Buchstabenfolgen die am meisten auftreten (mind. 2 mal) und möglichst lang sind.
In diesem Beispiel ist die Folge: ceg, die am meisten auftaucht. Aber wie könnte ein Algorithmus mit PHP Funktionen aussehen, der diese Problematik löst.

 

[chainy]

Ist nur ein Ansatz, keine Ahnung ob ich damit alle Möglichkeiten abdecke, aber es ist ja nicht so, dass man es noch ändern/erweitern kann.

$strSource = "cegabedecegcgbacceffgecegcdcegabceg";
$intLength = strlen($strSource);
$strTmp = null;
$arrCount = array();
for( $o = 0; $o < $intLength; $o++ )
{
	if( ($intLength-$o) <= 2 )
		continue;
  
	for( $i = 2; $i < ($intLength-$o); $i++ )
 	{  
		$strTmp = substr($strSource, $o, $i);
		$intCount = substr_count($strSource, $strTmp);
		if( $intCount >= 2 )
		{
			if(! array_key_exists($intCount, $arrCount) )
				$arrCount[ $intCount ] = array();
			
			$arrCount[ $intCount ][] = $strTmp;
		}
	}
}

foreach( $arrCount as $intCount => $arrResults )
	$arrCount[ $intCount ] = array_unique($arrResults);

var_dump($arrCount);

 

[chainy]

Beispielweise habe ich ein Alphabet von Buchstaben von a-g (a,b,c,d,e,f,g)
Und gegeben ist eine beliebige Anordung dieser Buchstaben, bspw.:

cegabedecegcgbacceffgecegcdcegabceg

Gefunden werden sollen nun Buchstabenfolgen die am meisten auftreten (mind. 2 mal) und möglichst lang sind.
In diesem Beispiel ist die Folge: ceg, die am meisten auftaucht. Aber wie könnte ein Algorithmus mit PHP Funktionen aussehen, der diese Problematik löst.

Also die längste Zeichenfolge, die am häufigsten vorkommt ist meines erachtens nach cegab und ecegc, kommen beide ganze 2 mal vor.

 

[NTDY]

Wow.
Sehr cool. Ich weiß zwar noch nicht genau was der Code macht, aber die ersten Tests mit

abcabc
abcdabce

funktionieren wunderbar.

Vielen Dank.

 

[chainy]

Ist eigentlich recht simpel, wenn du an der Stelle, an der mit substr gearbeitet wird, eine Ausgabe von $strTmp machst, wird dir ganz schnell klar, was da passiert.

[...]
$strTmp = substr($strSource, $o, $i);
var_dump($strTmp);
[...]

 

[Gumbo]

Wenn dich nur die längste Teilzeichenkette interessiert, sollte der Algorithmus bei Teilzeichenketten der Länge length-1 anfangen und die Länge in jedem Durchlauf dekrementieren.

 

[NTDY]

Hallo Gumbo,
vielen Dank für die Idee. Jetzt habe den Code von chainy dahingehend geändert, wie Du es angedacht hast.

<?php
$strSource = "cegabedecegcgbacceffgecegcdcegabceg";

$intLength = strlen($strSource);
$strTmp = null;
$arrCount = array();
for( $o = 0; $o < $intLength; $o++ ){

//keine Ahnung was das macht, braucht man das?
//    if(($intLength-$o) <= 2){
//        continue;
//	}
	for( $i = $intLength-$o; $i >=2; $i-- ){ 	
		$strTmp = substr($strSource,$o,$i);
		$intCount = substr_count($strSource,$strTmp);
        if($intCount >= 2 ){
			if(!array_key_exists($intCount, $arrCount)){
				$arrCount[$intCount] = array();			
            }
            $arrCount[$intCount][] = $strTmp;
        }
    }
}
foreach( $arrCount as $intCount => $arrResults ){
    $arrCount[$intCount] = array_unique($arrResults);
}
echo "<pre>";
var_dump($arrCount);  
echo "</pre>";
?>

Ich habe aber gerade keine Idee, wie ich in der for Schleife eine Anweisung einbringen soll, dass wenn ich bereits den längsten String 2 mal gefunden habe, dass er dann für diesen String und deren Untermengen, nicht mehr suchen braucht. Hast Du da vielleicht auch noch eine Idee?

 

[Gumbo]

Folgendes ist möglich:

$strSource = "cegabedecegcgbacceffgecegcdcegabceg";

$intLength = strlen($strSource);
$strTmp = null;
$arrCount = array();
for( $i=$intLength-1; $i>=2; $i-- ) {
	for( $o=0; $o<$intLength-$i; $o++ ) {
		$strTmp = substr($strSource, $o, $i);
		if( ($intCount = substr_count($strSource, $strTmp)) >= 2 ) {
			$arrCount[$strTmp] = $intCount;
		}
	}
	if( !empty($arrCount) ) {
		break;
	}
}
var_dump($arrCount);

 

[NTDY]

Vielen Dank an euch beide. Beide Algorithmen erfüllen auf ihre Weise die Bedingungen.

Besten Gruß