[PHP]算法-最长公共子串的PHP实现

<div class="cnblogs_code">

暴力解法思路：

1.<span style="color: #000000">以两个字符串的每个字符为开头，往后比较，这样就会需要两层循环

2.<span style="color: #000000">两层循环内部的比较方式，也是一层循环，以当前字符为起点，往后遍历比较，直到有不同就跳出这次循环，记录下相同子字符串的长度

3.以最长的那次长度为准，因此也就是有三层循环。时间复杂度O(n^3<span style="color: #000000">)

longest=0

<span style="color: #0000ff">for i=0;i<str1.size;i++

<span style="color: #0000ff">for j=0;j<str2.size;j++<span style="color: #000000">

m=i  n=j length=0

<span style="color: #0000ff">while(m<str1.size && n<str2.<span style="color: #000000">size)

<span style="color: #0000ff">if str1[m]!=str2[n] <span style="color: #0000ff">break

++<span style="color: #000000">length

++<span style="color: #000000">m

++<span style="color: #000000">n

longest=longest<length ? length:<span style="color: #000000">longest
动态规划法：

1.<span style="color: #000000">上面的比较过程中，以i和j为起点开始，如果遇到不同的停止后，下一次的开始位置会进行重复比较

2.动态规划法-空间换时间，矩阵图，可以把复杂度降至O(n^2<span style="color: #000000">)

3.<span style="color: #000000">str1是横轴，str2是纵轴，table[i][j]就是以这两个字符为结尾的最长子串的长度

4.table[0][j]可以推出，如果str1[0]==str2[j]的就为1，table[i][0]可以推出，如果str1[i]==str2[0<span style="color: #000000">] 就为1，其余为0

5.table[i][j]  如果str1[i]==str2[j] 可以由table[i-1][j-1]+1得到,<span style="color: #000000">不等就为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)这样的关系。

<div class="cnblogs_code">

<span style="color: #0000ff">function longestCommonSubstring1(<span style="color: #800080">$str1,<span style="color: #800080">$str2<span style="color: #000000">){

<span style="color: #800080">$longest=0<span style="color: #000000">;

<span style="color: #800080">$size1=<span style="color: #008080">strlen(<span style="color: #800080">$str1<span style="color: #000000">);

<span style="color: #800080">$size2=<span style="color: #008080">strlen(<span style="color: #800080">$str2<span style="color: #000000">);

<span style="color: #0000ff">for(<span style="color: #800080">$i=0;<span style="color: #800080">$i<<span style="color: #800080">$size1;<span style="color: #800080">$i++<span style="color: #000000">){

<span style="color: #0000ff">for(<span style="color: #800080">$j=0;<span style="color: #800080">$j<<span style="color: #800080">$size2;<span style="color: #800080">$j++<span style="color: #000000">){

<span style="color: #800080">$m=<span style="color: #800080">$i<span style="color: #000000">;

<span style="color: #800080">$n=<span style="color: #800080">$j<span style="color: #000000">;

<span style="color: #800080">$length=0<span style="color: #000000">;

<span style="color: #0000ff">while(<span style="color: #800080">$m<<span style="color: #800080">$size1 && <span style="color: #800080">$n<<span style="color: #800080">$size2<span style="color: #000000">){

<span style="color: #0000ff">if(<span style="color: #800080">$str1[<span style="color: #800080">$m]!=<span style="color: #800080">$str2[<span style="color: #800080">$n]) <span style="color: #0000ff">break<span style="color: #000000">;

++<span style="color: #800080">$length<span style="color: #000000">;

++<span style="color: #800080">$m<span style="color: #000000">;

++<span style="color: #800080">$n<span style="color: #000000">;

}

<span style="color: #800080">$longest=<span style="color: #800080">$longest < <span style="color: #800080">$length ? <span style="color: #800080">$length : <span style="color: #800080">$longest<span style="color: #000000">;

}

}

<span style="color: #0000ff">return <span style="color: #800080">$longest<span style="color: #000000">;

}

<span style="color: #008000">//<span style="color: #008000">矩阵动态规划法

<span style="color: #0000ff">function longestCommonSubstring2(<span style="color: #800080">$str1,<span style="color: #800080">$str2<span style="color: #000000">){

<span style="color: #800080">$size1=<span style="color: #008080">strlen(<span style="color: #800080">$str1<span style="color: #000000">);

<span style="color: #800080">$size2=<span style="color: #008080">strlen(<span style="color: #800080">$str2<span style="color: #000000">);

<span style="color: #800080">$table=<span style="color: #0000ff">array<span style="color: #000000">();

<span style="color: #0000ff">for(<span style="color: #800080">$i=0;<span style="color: #800080">$i<<span style="color: #800080">$size1;<span style="color: #800080">$i++<span style="color: #000000">){

<span style="color: #800080">$table[<span style="color: #800080">$i][0]=<span style="color: #800080">$str1[<span style="color: #800080">$i]==<span style="color: #800080">$str2[0] ? 1:0<span style="color: #000000">;

}

<span style="color: #0000ff">for(<span style="color: #800080">$j=0;<span style="color: #800080">$j<<span style="color: #800080">$size2;<span style="color: #800080">$j++<span style="color: #000000">){

<span style="color: #800080">$table[0][<span style="color: #800080">$j]=<span style="color: #800080">$str1[0]==<span style="color: #800080">$str2[<span style="color: #800080">$j] ? 1:0<span style="color: #000000">;

}

<span style="color: #0000ff">for(<span style="color: #800080">$i=1;<span style="color: #800080">$i<<span style="color: #800080">$size1;<span style="color: #800080">$i++<span style="color: #000000">){

<span style="color: #0000ff">for(<span style="color: #800080">$j=1;<span style="color: #800080">$j<<span style="color: #800080">$size2;<span style="color: #800080">$j++<span style="color: #000000">){

<span style="color: #0000ff">if(<span style="color: #800080">$str1[<span style="color: #800080">$i]==<span style="color: #800080">$str2[<span style="color: #800080">$j<span style="color: #000000">]){

<span style="color: #800080">$table[<span style="color: #800080">$i][<span style="color: #800080">$j]=<span style="color: #800080">$table[<span style="color: #800080">$i-1][<span style="color: #800080">$j-1]+1<span style="color: #000000">;

}<span style="color: #0000ff">else<span style="color: #000000">{

<span style="color: #800080">$table[<span style="color: #800080">$i][<span style="color: #800080">$j]=0<span style="color: #000000">;

}

}

}

<span style="color: #800080">$longest=0<span style="color: #000000">;

<span style="color: #0000ff">for(<span style="color: #800080">$i=0;<span style="color: #800080">$i<<span style="color: #800080">$size1;<span style="color: #800080">$i++<span style="color: #000000">){

<span style="color: #0000ff">for(<span style="color: #800080">$j=0;<span style="color: #800080">$j<<span style="color: #800080">$size2;<span style="color: #800080">$j++<span style="color: #000000">){

<span style="color: #800080">$longest=<span style="color: #800080">$longest<<span style="color: #800080">$table[<span style="color: #800080">$i][<span style="color: #800080">$j] ? <span style="color: #800080">$table[<span style="color: #800080">$i][<span style="color: #800080">$j] : <span style="color: #800080">$longest<span style="color: #000000">;

}}

<span style="color: #0000ff">return <span style="color: #800080">$longest<span style="color: #000000">;

}

<span style="color: #800080">$len=longestCommonSubstring1(<span style="color: #800080">$str1,<span style="color: #800080">$str2<span style="color: #000000">);

<span style="color: #800080">$len=longestCommonSubstring2(<span style="color: #800080">$str1,<span style="color: #800080">$str2<span style="color: #000000">);

<span style="color: #008080">var_dump(<span style="color: #800080">$len);

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!