String Searching

### Program Information

Name: String Searching
Domain: Algorithm
Functionality: String Searching Algorithm like BM,KMP,RK.
Input: $X=x_1x_2\cdots$ is a string,the pattern to search for is pattern $K=k_1k_2\cdots$.And the input denotes as $(X,K)$
Output: The output $O(X,K)$ of the matching algorithm is the index,in $X$, of the first matching occurrence if $K$ is found in $X$,and -1 if $K$ is not found.

#### Reference

 Using Metamorphic Testing to Improve Dynamic Symbolic Execution  https://doi.org/10.1109/ASWEC.2015.16

### MR Information

#### MR1------ Concatenation

Description:
Property: $O(X,K) \neq -1 \Rightarrow O(X+X') \neq -1$
Source input: $(X,K)$
Source output: $O(X,K)$
Follow-up input: $(X+X',K)$
Follow-up output: $O(X+X',K)$
Input relation: $(X,K) \Rightarrow (X+X',K)$
Output relation: $O(X,K) \neq -1 \Rightarrow O(X+X') \neq -1$
Pattern:

#### MR2------ Interleaving

Description:
Property: $\exists z:(z \notin X \wedge X'=x_1zx_2z\cdots z) \wedge O(X,K) \neq -1 \Rightarrow O(X',K) = -1$
Source input: $(X,K)$
Source output: $O(X,K)$
Follow-up input: $(X',K)$
Follow-up output: $O(X',K)$
Input relation: $(X,K) \Rightarrow (X',K)$
Output relation: $\exists z:(z \notin X \wedge X'=x_1zx_2z\cdots z) \wedge O(X,K) \neq -1 \Rightarrow O(X',K) = -1$
Pattern:

#### MR3------ Reversal

Description:
Property: $O(X,K) \neq -1 \Rightarrow O(reverse(X),reverse(K')) \neq -1$
Source input: $(X,K)$
Source output:  $O(X,K)$
Follow-up input: $(reverse(X),reverse(K'))$
Follow-up output: $O(reverse(X),reverse(K'))$
Input relation: $(X,K) \Rightarrow (reverse(X),reverse(K'))$
Output relation: $O(X,K) \neq -1 \Rightarrow O(reverse(X),reverse(K')) \neq -1$
Pattern:

#### MR4------Character case conversion

Description:
Property: $O(X,K) \neq -1 \Rightarrow O(toLower(X),toLower(K)) \neq -1$
Source input: $(X,K)$
Source output:  $O(X,K)$
Follow-up input: $(toLower(X),toLower(K))$
Follow-up output: $O(toLower(X),toLower(K))$
Input relation:  $(X,K) \Rightarrow (toLower(X),toLower(K))$
Output relation: $O(X,K) \neq -1 \Rightarrow O(toLower(X),toLower(K)) \neq -1$
Pattern:
Insert title here