Approximate string matching

### Program Information

Name: Approximate string matching
Domain: Algorithm
Functionality: Determines the approximate equality between two strings using 12 different algorithms such as Longest Common Subsequence, and Sørensen-Dice Distance.
Input: Assume that $X=x_1x_2\cdots$ is the source string to be matched,$Y=y_1y_2\cdots$ is the target string to be matched with,$t\in \{strong,weak,normal\}$ is the tolerance level,$ip$ is the algorithm used.
Output: Output $O(X,Y,t,op)$ is true if and only if the two strings are approximately matched according to tolerance level $t$.

#### Reference

Generating Source Inputs for Metamorphic Testing Using Dynamic Symbolic Execution https://doi.org/10.1145/2896971.2896980

### MR Information

#### MR1------Reversal

Description:
Property: $X'=reverse(X)\&Y'=reverse(Y) \Rightarrow O(X,Y,t,op) = O(X',Y',t,op)$
Source input: $(X,Y,t,op)$
Source output: $O(X,Y,t,op)$
Follow-up input: $(X',Y',t,op)$
Follow-up output: $O(X',Y',t,op)$
Input relation: $X'=reverse(X)\&Y'=reverse(Y)$
Output relation: $O(X,Y,t,op) = O(X',Y',t,op)$
Pattern:

#### MR2------Limit cases

Description:
Property: $t\neq weak \Rightarrow O(X,'\ ',t,op) = false \wedge O(X,X,t,op) = true$
Source input: $(X,X,t,op)$
Source output: $O(X,X,t,op)$
Follow-up input: $(X,'\ ',t,op)$
Follow-up output: $O(X,'\ ',t,op)$
Input relation: $(X,X,t,op) \Rightarrow (X,'\ ',t,op)$ where $t\neq weak$
Output relation: $O(X,'\ ',t,op) = false \wedge O(X,X,t,op) = true$
Pattern:

#### MR3------Monotonicity

Description:
Property: $O(X,Y,strong,op) = true \Rightarrow O(X,Y,normal,op)=O(X,Y,weak,op) = true$
Source input: $(X,Y,strong,op)$
Source output: $O(X,Y,strong,op)$
Follow-up input: $(X,Y,normal,op),(X,Y,weak,op)$
Follow-up output: $O(X,Y,normal,op),O(X,Y,weak,op)$
Input relation: $O(X,Y,strong,op) = true$
Output relation: $O(X,Y,normal,op)=O(X,Y,weak,op) = true$
Pattern:
Insert title here