header
the string searching program

Tag:
Edit edit   Starstar

Program Information

Name: the string searching program
Domain: algorithm
Functionality: to search string
Input: $X = x1x2 ···$(type:string): the string to search for. $K = k1k2 ···$: the pattern to search for. Assume that $X = x1x2 ···$ is a string, the pattern to search for is pattern $K = k1k2 ···$
Output: $O(X,K)$: the index, if the index is found, then the index = X, otherwise, the index = -1

Reference


    Using metamorphic testing to improve dynamic symbolic execution.
    https://dx.doi.org/10.1109/MET.2016.012


MR Information

MR1------

Description:
Property: Concatenation: $(O(X, K)\neq -1)\Rightarrow (O(X++X', K)\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: Concatenation
Output relation: $(O(X, K)\neq -1)\Rightarrow (O(X++X', K)\neq -1)$
Pattern: symmetry, add noise

MR2------

Description:
Property: Interleaving: $\exists z:(z\notin X \land X'=x1zx2z...z) \land 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:
Output relation: $\exists z:(z\notin X \land X'=x1zx2z...z) \land O(X,K)\neq -1\Rightarrow O(X',K)=-1 $
Pattern: symmetry

MR3------

Description:
Property: Reversal:$(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: reversal
Output relation: $(O(X, K)\neq -1)\Rightarrow O(reverse(X), reverse(K'))\neq -1$
Pattern: symmetry, change direction

MR4------

Description:
Property: Character case conversion:$(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: Character case conversion
Output relation: $(O(X, K)\neq -1)\Rightarrow O(toLower(X), toLower(K))\neq -1$
Pattern: symmetry, replacement
Insert title here