6
$\begingroup$

This looks like quite the challenge; given a pattern $P$ (of length $n$) and a string $S$ (of length $m$), how would you check whether the string matches the pattern? For instance:

  • If $P$ = "xyx" and $S$ = "foobarfoo" then $S$ matches $P.$
  • If $P$ = "acca" and $S$ = "carbuscarbus" then $S$ does not match $P.$

My thoughts so far: This looks like a dynamic programming problem. We can define a boolean

$M(i, j)$ = True iff pattern $P[i:n]$ matches $S[j:m]$

We then need $M(0, 0).$ Note here that the substring notation is $P[i:n] = P_iP_{i+1}...P_n$.

I couldn't think of an efficient recurrence beyond this. It seems like I would have to introduce an extra mapping (from a substring of $P$ to a substring of $S$, indicating that the earlier "matches" the latter; for example in the first example, ("x", "foo") would be part of the mapping. You then replace "x" by "foo" in the substring of P). This would make it $O(2^n)$ or worse though.

If you don't see the intuitive meaning, here's a more rigorous definition: S matches P iff there exists a mapping $$T : P[i:j] \rightarrow S[a:b]$$ for $i, j \in [1, 2 ...n]$ and $a, b \in [1, 2 ...m]$, such that replacing $P[i:j]$ with $S[a:b]$ transforms P into S. For example, in the first case where $P$ = "xyx" and $S$ = "foobarfoo", $T$ is as follows:

  • T('x') = 'foo'. {Here $i = 1, j = 1, a = 1, b = 3$}
  • T('y') = 'bar'. {Here $i = 2, j = 2, a = 4, b = 6$}

Replacing all instances (in $P$) of 'x' with 'foo' and 'y' with 'bar', gives us 'foobarfoo' i.e. $S$.

Thus, $S$ matches $P.$

$\endgroup$
  • 1
    $\begingroup$ It seems that your problem can be described as building suffix tree and then looking for prefixes, which for patterns like "xyx" or "acca" is linear. With more involving patterns it may grow to quadratic case. The worst case as you have noticed may grow to exponential case (backtracking). Are you interested only in yes/no check or want the pattern to be mapped into string? If string then what will ne the output for "xyx" pattern and "abbcaacbbaabbcaacbba" string? $\endgroup$ – Evil Oct 1 '16 at 21:23
  • 1
    $\begingroup$ The mapping is called a string homomorphism. Given $P,S$, you want to know whether there exists a string homomorphism $f$ such that $f(P)=S$. $\endgroup$ – D.W. Oct 2 '16 at 0:15
  • 1
    $\begingroup$ @Evil I'm only looking for a yes/no check. $\endgroup$ – Mathguy Oct 2 '16 at 6:23
4
$\begingroup$

There are various algorithms for pattern matching in string.

Exact String matching algorithms

  1. Brute Force
  2. Rabin Karp
  3. Boyer-Moree
  4. KMP
  5. Aho Corasick etc.

Approximate String Matching Algorithm

Approximate String matching is applied in text searching, pattern recognition and signal processing applications. For a text T[1..n] and pattern P[1...m], we are supposed to find all the occurrences of pattern in the text whose edit distance to the pattern is at most K. The edit distance between two strings is defined as minimum number of character insertion, deletion and replacements needed to make them equal.

Approximate string matching problem is solved with the help of dynamic programming.

You can have a look through all these algorithms. These algorithms will take optimum complexity like O(m),O(n+m) (in case of KMP for example).

$\endgroup$
  • 2
    $\begingroup$ thank you for your answer. It does not however answer my question. I am not looking for string searching algorithms; I'm looking for a different kind of pattern matching. Please can you read the examples again? $\endgroup$ – Mathguy Oct 1 '16 at 2:26
  • 1
    $\begingroup$ This might be used to solve subproblem of matching (discarding brute force). And approximate matching is not relevant to this problem at all. $\endgroup$ – Evil Oct 1 '16 at 22:27
  • 1
    $\begingroup$ This answer is no longer relevant, now that the question was modified. (A good reason to make sure the original version of the question is as clear as possible, from the start..) $\endgroup$ – D.W. Oct 2 '16 at 0:06
  • 1
    $\begingroup$ @D.W. Before editing the question too, the examples made it ample clear that I wasn't talking about string searching! It's a more 'indirect' matching in both the examples. The edit was more about adding some mathematical formalism to help others generalise known algorithms to this problem :) $\endgroup$ – Mathguy Oct 2 '16 at 6:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.