## 3 Implementation of the Algorithm  
According to Theorem 1, our new algorithm for computing \(f(i,j,k)\) is a standard dynamic programming algorithm. With the recursive Formula (2), the new dynamic programming algorithm for computing \(f(i,j,k)\) can be implemented as the following Algorithm 1.  
To implement our new algorithm efficiently, it is important to compute \(\sigma(P[1:k]\oplus x_{i})\) for each \(0\leq k<r\) and \(x_{i}\), where \(1\leq i\leq n\) efficiently in line 8.  
It is clear that \(\sigma(P[1:k]\oplus x_{i})=k+1\) when \(x_{i}=p_{k+1}\). It will be more complex to compute \(\sigma(P[1:k]\oplus x_{i})\) when \(x_{i}\
eq p_{k+1}\). In this case, the length of the matched prefix of \(P\) must be shortened to the largest \(t<k\), such that \(p_{k-t+1}\cdots p_{k}=p_{1}\cdots p_{t}\) and \(x_{i}=p_{t+1}\). Therefore, in this case, \(\sigma(P[1:k]\oplus x_{i})=t+1\).  
This computation is very similar to the computation of the prefix function in the Knuth-CMorris-CPratt string searching algorithm (KMP algorithm) for solving the string matching problem [8].  
To accelerate the processing, we can pre-compute a table, \(\lambda(k,ch)\), of the function, \(\sigma(P[1:k]\oplus ch)\), for each character, \(ch\in\sum\) and \(1\leq k\leq r\). It is clear that \(\lambda(k-1,P[k])=k\) for each \(1\leq k\leq r\). The other values of the table, \(\lambda\), can be computed by using the prefix function, \(kmp\), in the following recursive Algorithm 4.
```
0: String \(P=p_{1}\cdots p_{r}\), integer \(k\) and character \(ch\)
0:\(\sigma(P[1:k]\oplus ch)\)
1:while\(k\geq 0\;\;p_{k+1}\
eq ch\)do
2:\(k\gets kmp(k)\)
3:endwhile
4:return\(k+1\)
```
**Algorithm 3**\(\sigma(k,ch)\).
```
0: Integer \(k\), character \(ch\)
0: Value of \(\lambda(k,ch)\)
1:if\(k>0\;\lambda(k,ch)=0\)then
2:\(\lambda(k,ch)\leftarrow\lambda(kmp(k),ch)\)
3:endif
4:return\(\lambda(k,ch)\)
```  
**Algorithm 4**\(\lambda(k,ch)\).  
The time cost of the above preprocessing algorithm is clearly \(O(r|\Sigma|)\). By using this pre-computed table, \(\lambda\), the value of function \(\sigma(P[1:k]\oplus ch)\) for each character, \(ch\in\sum\) and \(1\leq k<r\), can be computed readily in \(O(1)\) time.  
With this pre-computed table, \(\lambda\), the loop body of the above Algorithm 1 requires only \(O(1)\) time, because \(\lambda(k,x_{i})\) can be computed in \(O(1)\) time for each \(x_{i},1\leq i\leq n\) and any \(0\leq k<r\). Therefore, our new algorithm for computing the length of an LCS of \(X\) and \(Y\) that excludes \(P\) as a substring requires \(O(nmr)\) time and \(O(r|\Sigma|)\) preprocessing time.  
If we want to obtain the actual LCS of \(X\) and \(Y\) that excludes \(P\) as a substring, not only its length, we can also present a simple recursive back-tracing algorithm for this purpose as Algorithm 5.  
At the end of our new algorithm, a function call, \(\mathit{back}(1,1,0)\), will produce the resultant LCS accordingly.  
Because the cost of the computation of \(\lambda(k,x_{i})\) is \(O(1)\), the algorithm, \(\mathit{back}(i,j,k)\), will cost \(O(n+m)\) in the worst case.  
Finally, we summarize our results in the following theorem:  
**Theorem 2**: _Algorithm 1 solves the STR-EC-LCS problem correctly in \(O(nmr)\) time and \(O(nmr)\) space, with preprocessing time \(O(r|\Sigma|)\)._