이 기사에서 제공하는 내용은 PHP 알고리즘에서 가장 긴 공통 하위 문자열의 PHP 구현 문제입니다. 도움이 필요한 친구들이 참고할 수 있기를 바랍니다.
가장 긴 공통 부분 문자열 문제:
두 개의 문자열이 주어졌을 때, 두 문자열 사이에서 가장 긴 동일한 부분 문자열의 길이를 구하세요.
폭력적인 해결책 아이디어:
1. 두 문자열의 각 문자로 시작하여 나중에 비교합니다. 이를 위해서는 두 수준의 루프가 필요합니다.
2. 2단계 루프 내부의 비교 방법도 1단계 루프입니다. , 현재 문자부터 시작하여 차이가 있을 때까지 순회하고 비교한 다음 루프에서 벗어나 동일한 하위 문자열의 길이를 기록합니다
3. 가장 긴 길이가 우선하므로 세 가지 수준의 루프가 있습니다. 시간 복잡도 O(n^3)
longest=0 for i=0;i<str1.size;i++ for j=0;j<str2.size;j++ m=i n=j length=0 while(m<str1.size && n<str2.size) if str1[m]!=str2[n] break ++length ++m ++n longest=longest<length ? length:longest
동적 프로그래밍 방법:
1 위의 비교 과정에서 i와 j부터 시작하여 서로 다른 정지점을 만나면 다음 시작 위치는 반복 비교
2입니다. 동적 프로그래밍 방법 - 시간에 대한 공간, 행렬 그래프는 복잡성을 O(n^2)
3으로 줄일 수 있습니다.str1은 가로 축, str2는 세로 축, table[i][j ]는 길이입니다. str1[0]==str2[j]가 1이면 table[i][ 0]은 str1이면 추론할 수 있습니다. [i]==str2[0]은 1이고 나머지는 0
5.table[i][j] str1[i]==str2[j]를 table[i -1][로 계산할 수 있는 경우 j-1]+1을 구하고, 같지 않으면 0
두 문자열이 각각 s와 t라고 가정하고, s[i]와 t[j]는 각각 i번째와 j번째 문자를 나타냅니다( 문자 순서는 0부터 시작), L[i, j]는 s[i] 및 s[j]로 끝나는 동일한 하위 문자열의 최대 길이를 나타냅니다. L[i, j]와 L[i+1,j+1] 사이의 관계를 추론하는 것은 어렵지 않습니다. 둘 사이의 유일한 차이점은 문자 쌍 s[i+1]과 t[j이기 때문입니다. +1] . s[i+1]과 t[j+1]이 다르면 L[i+1, j+1]은 당연히 0이 되어야 합니다. 왜냐하면 이들로 끝나는 부분 문자열은 정확히 동일할 수 없고 s [i인 경우에도 마찬가지입니다. +1]과 t[j+1]은 동일합니다. 그런 다음 s[i] 및 t[j]로 끝나는 가장 긴 동일한 하위 문자열 뒤에 이 두 문자를 추가하면 길이가 한 명 더 추가됩니다. 위의 두 가지 상황을 결합하면 L[i+1,j+1]=(s[i]==t[j]?L[i,j]+1:0) 관계를 얻습니다.
코드 예:<?php
$str1="abcdef";
$str2="esdfdbcde1";
//暴力解法
function longestCommonSubstring1($str1,$str2){
$longest=0;
$size1=strlen($str1);
$size2=strlen($str2);
for($i=0;$i<$size1;$i++){
for($j=0;$j<$size2;$j++){
$m=$i;
$n=$j;
$length=0;
while($m<$size1 && $n<$size2){
if($str1[$m]!=$str2[$n]) break;
++$length;
++$m;
++$n;
}
$longest=$longest < $length ? $length : $longest;
}
}
return $longest;
}
//矩阵动态规划法
function longestCommonSubstring2($str1,$str2){
$size1=strlen($str1);
$size2=strlen($str2);
$table=array();
for($i=0;$i<$size1;$i++){
$table[$i][0]=$str1[$i]==$str2[0] ? 1:0;
}
for($j=0;$j<$size2;$j++){
$table[0][$j]=$str1[0]==$str2[$j] ? 1:0;
}
for($i=1;$i<$size1;$i++){
for($j=1;$j<$size2;$j++){
if($str1[$i]==$str2[$j]){
$table[$i][$j]=$table[$i-1][$j-1]+1;
}else{
$table[$i][$j]=0;
}
}
}
$longest=0;
for($i=0;$i<$size1;$i++){
for($j=0;$j<$size2;$j++){
$longest=$longest<$table[$i][$j] ? $table[$i][$j] : $longest;
}}
return $longest;
}
$len=longestCommonSubstring1($str1,$str2);
$len=longestCommonSubstring2($str1,$str2);
var_dump($len);
위는 이 기사의 전체 내용입니다. 더 많은 관련 튜토리얼을 보려면
, php 실용 비디오 튜토리얼, bootstrap을 방문하세요. 비디오 튜토리얼!
위 내용은 PHP 알고리즘: PHP는 가장 긴 공통 부분 문자열 문제를 구현합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!