So berechnen Sie den Abstand zwischen Zeichenfolgen mit PHP-PHP-Tutorial-php.cn

So berechnen Sie den Abstand zwischen Zeichenfolgen mit PHP

不言

Freigeben： 2023-04-02 21:58:01

Original

1589 Leute haben es durchsucht

Dieser Artikel stellt hauptsächlich die Verwendung von PHP zur Berechnung des Abstands zwischen Zeichenfolgen vor. Jetzt kann ich ihn mit Ihnen teilen

Zusammenfassung

Zusammenfassung in einem Satz: Wie lässt sich das DP-Problem am besten lösen: Analysieren Sie den Status und zeichnen Sie dann ein Beispiel + zeichnen Sie eine Tabelle.

1. Wie lässt sich das DP-Problem am besten lösen?

Nach der Analyse des Status, Beispiel + Zeichentabelle

2. Welche Vorteile hat das Zeichnen?

Nach dem Zeichnen der Tabelle ist es einfach zu programmieren und es ist nicht leicht, Fehler zu machen, da Sie eine Referenz haben, können Sie den Code entsprechend der Referenz schreiben

2 Abstand der Zeichenfolge

Titelbeschreibung

Levenshtein-Abstand, auch Bearbeitungsabstand genannt, bezieht sich auf die minimale Anzahl von Bearbeitungsvorgängen, die erforderlich sind, um zwischen zwei Zeichenfolgen eine Zeichenfolge in die andere umzuwandeln. Zu den zulässigen Bearbeitungsvorgängen gehören das Ersetzen eines Zeichens durch ein anderes, das Einfügen eines Zeichens und das Löschen eines Zeichens. Der Algorithmus zur Bearbeitung der Distanz wurde erstmals vom russischen Wissenschaftler Levenshtein vorgeschlagen und wird daher auch Levenshtein-Distanz genannt.

Beispiel:

String A: abcdefg

String B: abcdef

Erreichen Sie den Zweck, indem Sie das Zeichen „g“ hinzufügen oder löschen. Beide Optionen erfordern einen Vorgang. Definieren Sie die Häufigkeit, die für diesen Vorgang erforderlich ist, als Abstand zwischen zwei Zeichenfolgen.

Anforderung:

Schreiben Sie für zwei beliebige Zeichenfolgen einen Algorithmus, um deren Bearbeitungsentfernung zu berechnen.

Bitte implementieren Sie die folgende Schnittstelle

/*  功能：计算两个字符串的距离
 *  输入： 字符串A和字符串B
 *  输出：无
 *  返回：如果成功计算出字符串的距离，否则返回-1
 */
     public   static   int calStringDistance (String charA, String  charB)
    {
        return  0;
    }

Nach dem Login kopieren

Eingabebeschreibung:

Geben Sie zwei Zeichenfolgen ein

Ausgabebeschreibung:

Berechnungsergebnis abrufen

Beispiel 1

Eingabe

abcdefg
abcdef

Nach dem Login kopieren

Ausgabe

Nach dem Login kopieren

2. Code (der Code ist falsch)

<?php
/*
1、这是一个dp的题目
2、而且是一个线性dp
3、f(i)(j)怎么得到f(i)(j)
4、dp就是刷表，这里明显是刷2维表
5、f(i)(j)表示什么呢：表示字符串1的前i和字符串2的前就j个的距离，那么最终所有就是f(len(str1))(len(str2))
6、状态转移方程呢：如果字符串1的最后一个和字符串2的最后一个字符相等，那么f(i)(j)=f(i-1)(j-1)，
不相等，那么f(i)(j)=min(f(i-1)(j),f(i)(j-1))
7、想的差不都的时候就直接到excel中根据实例画表即可，不容易出错且清晰快
*/
while($str1=trim(fgets(STDIN))){
    $str2=trim(fgets(STDIN));
    $len1=strlen($str1);
    $len2=strlen($str2);
    $dp=null;
    for($i=0;$i<=$len2;$i++){
        $dp[]=array_fill(0,intval($len1)+1,0);
    }
    for($i=0;$i<=$len1;$i++){
        $dp[0][$i]=$i;
    }
    for($i=0;$i<=$len2;$i++){
        $dp[$i][0]=$i;
    }
    for($i=1;$i<=$len2;$i++){//行
        for($j=1;$j<=$len1;$j++){//列
            //如果str1[$i-1]在str2:0-$j-1中找到，
            $str1_2=substr($str1,0,$j);
            if(strpos($str1_2,$str2[$i-1])!==false){
                $dp[$i][$j]=$dp[$i-1][$j-1];
            }else{
                $dp[$i][$j]=max($dp[$i][$j-1],$dp[$i-1][$j]);
            }
        }
    }
    echo $dp[$len2][$len1].PHP_EOL;
    //print_r($dp);
}
?>

Nach dem Login kopieren

Das Obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, er wird für das Studium aller hilfreich sein. Weitere verwandte Inhalte finden Sie auf der chinesischen PHP-Website.

Verwandte Empfehlungen:

So verwenden Sie PHP, um die Analyse von Bildern in Dokumenten zu erhalten

PHP implementiert einfach das Senden und Verhindern von E-Mails von der Behandlung als Spam-Verarbeitung

So ändern Sie die WordPress-Bildadresse in einen relativen Pfad

Das obige ist der detaillierte Inhalt vonSo berechnen Sie den Abstand zwischen Zeichenfolgen mit PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!