PHP 알고리즘: PHP는 가장 긴 공통 부분 문자열 문제를 구현합니다.

이 기사에서 제공하는 내용은 PHP 알고리즘에서 가장 긴 공통 하위 문자열의 PHP 구현 문제입니다. 도움이 필요한 친구들이 참고할 수 있기를 바랍니다.

가장 긴 공통 부분 문자열 문제:

두 개의 문자열이 주어졌을 때, 두 문자열 사이에서 가장 긴 동일한 부분 문자열의 길이를 구하세요.

폭력적인 해결책 아이디어:

1. 두 문자열의 각 문자로 시작하여 나중에 비교합니다. 이를 위해서는 두 수준의 루프가 필요합니다.

2. 2단계 루프 내부의 비교 방법도 1단계 루프입니다. , 현재 문자부터 시작하여 차이가 있을 때까지 순회하고 비교한 다음 루프에서 벗어나 동일한 하위 문자열의 길이를 기록합니다

3. 가장 긴 길이가 우선하므로 세 가지 수준의 루프가 있습니다. 시간 복잡도 O(n^3)

longest=0 for i=0;i
        

         로그인 후 복사
        
       

동적 프로그래밍 방법:

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) 관계를 얻습니다.