📄 lcs.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd"><html><head> <title>Description of lcs</title> <meta name="keywords" content="lcs"> <meta name="description" content="lcs: Longest (maximum) common subsequence"> <meta http-equiv="Content-Type" content="text/html; charset=big5"> <meta name="generator" content="m2html © 2003 Guillaume Flandin"> <meta name="robots" content="index, follow"> <link type="text/css" rel="stylesheet" href="../m2html.css"></head><body><a name="_top"></a><div><a href="../index.html">Home</a> > <a href="index.html">dcpr</a> > lcs.m</div><!--<table width="100%"><tr><td align="left"><a href="../index.html"><img alt="<" border="0" src="../left.png"> Master index</a></td><td align="right"><a href="index.html">Index for dcpr <img alt=">" border="0" src="../right.png"></a></td></tr></table>--><h1>lcs</h1><h2><a name="_name"></a>PURPOSE <a href="#_top"><img alt="^" border="0" src="../up.png"></a></h2><div class="box"><strong>lcs: Longest (maximum) common subsequence</strong></div><h2><a name="_synopsis"></a>SYNOPSIS <a href="#_top"><img alt="^" border="0" src="../up.png"></a></h2><div class="box"><strong>function [lcsCount, lcsPath, lcsStr, lcsTable] = lcs(a, b, plotOpt) </strong></div><h2><a name="_description"></a>DESCRIPTION <a href="#_top"><img alt="^" border="0" src="../up.png"></a></h2><div class="fragment"><pre class="comment">lcs: Longest (maximum) common subsequence
Usage: [count, lcsPath, lcsStr, lcsTable] = lcsm(a, b, plotOpt)
a: input string 1
b: input string 2
plotOpt: plot option
lcsCount: count of LCS
lcsPath: optimal path of dynamical programming through the lcs table
lcsStr: LCS string
lcsTable: LCS table for applying dynamic programming
Type "lcs" for a self-demo.</pre></div><!-- crossreference --><h2><a name="_cross"></a>CROSS-REFERENCE INFORMATION <a href="#_top"><img alt="^" border="0" src="../up.png"></a></h2>This function calls:<ul style="list-style-image:url(../matlabicon.gif)"><li><a href="dpPathPlot4strMatch.html" class="code" title="function dpPathPlot4strMatch(str1, str2, lcsPath, lcsTable, prevx, prevy)">dpPathPlot4strMatch</a> dpPathPlot4strMatch: Plot the path of dynamic programming for string match.</li></ul>This function is called by:<ul style="list-style-image:url(../matlabicon.gif)"></ul><!-- crossreference --><h2><a name="_subfunctions"></a>SUBFUNCTIONS <a href="#_top"><img alt="^" border="0" src="../up.png"></a></h2><ul style="list-style-image:url(../matlabicon.gif)"><li><a href="#_sub1" class="code">function selfdemo</a></li></ul><h2><a name="_source"></a>SOURCE CODE <a href="#_top"><img alt="^" border="0" src="../up.png"></a></h2><div class="fragment"><pre>0001 <a name="_sub0" href="#_subfunctions" class="code">function [lcsCount, lcsPath, lcsStr, lcsTable] = lcs(a, b, plotOpt)</a>0002 <span class="comment">%lcs: Longest (maximum) common subsequence</span>0003 <span class="comment">% Usage: [count, lcsPath, lcsStr, lcsTable] = lcsm(a, b, plotOpt)</span>0004 <span class="comment">% a: input string 1</span>0005 <span class="comment">% b: input string 2</span>0006 <span class="comment">% plotOpt: plot option</span>0007 <span class="comment">% lcsCount: count of LCS</span>0008 <span class="comment">% lcsPath: optimal path of dynamical programming through the lcs table</span>0009 <span class="comment">% lcsStr: LCS string</span>0010 <span class="comment">% lcsTable: LCS table for applying dynamic programming</span>0011 <span class="comment">%</span>0012 <span class="comment">% Type "lcs" for a self-demo.</span>0013 0014 <span class="comment">% Roger Jang, 981226, 990409, 20060528, 20081009</span>0015 0016 <span class="keyword">if</span> nargin<1, <a href="#_sub1" class="code" title="subfunction selfdemo">selfdemo</a>; <span class="keyword">return</span>; <span class="keyword">end</span>0017 <span class="keyword">if</span> nargin<3, plotOpt=0; <span class="keyword">end</span>0018 0019 a=a(:)'; m=length(a);0020 b=b(:)'; n=length(b);0021 lcsTable=zeros(m, n);0022 prevx=zeros(m, n);0023 prevy=zeros(m, n);0024 cost=zeros(3,1);0025 <span class="comment">% Compute the first element</span>0026 lcsTable(1,1)=a(1)==b(1);0027 prevx(1,1)=0; <span class="comment">% not plotted</span>0028 prevy(1,1)=0; <span class="comment">% not plotted</span>0029 <span class="comment">% Compute the first row & column</span>0030 <span class="keyword">for</span> i=2:m0031 <span class="keyword">if</span> a(i)==b(1)0032 lcsTable(i,1)=1;0033 prevx(i,1)=i-1;0034 prevy(i,1)=0;0035 <span class="keyword">else</span>0036 lcsTable(i,1)=lcsTable(i-1,1);0037 prevx(i,1)=i-1;0038 prevy(i,1)=1;0039 <span class="keyword">end</span>0040 <span class="keyword">end</span>0041 <span class="keyword">for</span> j=2:n0042 <span class="keyword">if</span> a(1)==b(j)0043 lcsTable(1,j)=1;0044 prevx(1,j) = 0;0045 prevy(1,j) = j-1;0046 <span class="keyword">else</span>0047 lcsTable(1,j)=lcsTable(1,j-1);0048 prevx(1,j) = 1;0049 prevy(1,j) = j-1;0050 <span class="keyword">end</span>0051 0052 <span class="keyword">end</span>0053 <span class="comment">% Compute all the other elements</span>0054 <span class="keyword">for</span> i=2:m,0055 <span class="keyword">for</span> j=2:n,0056 <span class="keyword">if</span> a(i)==b(j)0057 lcsTable(i,j)=lcsTable(i-1,j-1)+1;0058 prevx(i,j)=i-1;0059 prevy(i,j)=j-1;0060 <span class="keyword">else</span>0061 [lcsTable(i,j), index]=max([lcsTable(i-1, j), lcsTable(i, j-1)]);0062 <span class="keyword">switch</span> index0063 <span class="keyword">case</span> 10064 prevx(i,j)=i-1;0065 prevy(i,j)=j;0066 <span class="keyword">case</span> 20067 prevx(i,j)=i;0068 prevy(i,j)=j-1;0069 <span class="keyword">end</span>0070 <span class="keyword">end</span>0071 <span class="keyword">end</span>0072 <span class="keyword">end</span>0073 0074 <span class="comment">% ====== Return length of ED string</span>0075 lcsCount = lcsTable(m, n);0076 0077 <span class="comment">% ====== Return the optimal path of the dynamical programming</span>0078 <span class="keyword">if</span> nargout>1 | plotOpt0079 now = [m, n];0080 prev = [prevx(now(1), now(2)), prevy(now(1), now(2))];0081 lcsPath = now;0082 <span class="keyword">while</span> all(prev>0)0083 now = prev;0084 prev = [prevx(now(1), now(2)), prevy(now(1), now(2))];0085 lcsPath = [lcsPath; now];0086 <span class="keyword">end</span> 0087 lcsPath = flipud(lcsPath);0088 <span class="keyword">end</span>0089 0090 <span class="comment">% ====== Return the LCS string</span>0091 <span class="keyword">if</span> nargout>2 | plotOpt <span class="comment">% return LCS string</span>0092 temp = lcsTable((lcsPath(:,2)-1)*m+lcsPath(:,1)); <span class="comment">% LCS count along the path</span>0093 temp = [0; temp];0094 index = find(diff(temp));0095 lcsStr = a(lcsPath(index,1));0096 <span class="keyword">end</span>0097 0098 <span class="comment">% ====== Plot</span>0099 <span class="keyword">if</span> plotOpt0100 <a href="dpPathPlot4strMatch.html" class="code" title="function dpPathPlot4strMatch(str1, str2, lcsPath, lcsTable, prevx, prevy)">dpPathPlot4strMatch</a>(a, b, lcsPath, lcsTable, prevx, prevy);0101 title(sprintf(<span class="string">'LCS = %s'</span>, lcsStr));0102 <span class="keyword">end</span>0103 0104 <span class="comment">% ====== Self demo</span>0105 <a name="_sub1" href="#_subfunctions" class="code">function selfdemo</a>0106 str1=<span class="string">'elimination'</span>;0107 str2=<span class="string">'religious'</span>;0108 plotOpt=1;0109 [lcsCount, lcsPath, lcsStr, lcsTable] = feval(mfilename, str1, str2, plotOpt);</pre></div><hr><address>Generated on Thu 30-Oct-2008 12:53:56 by <strong><a href="http://www.artefact.tk/software/matlab/m2html/">m2html</a></strong> © 2003</address></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -