CLR cover
Previous problem

Problem 32: Parameterised Matching

Next problem

The problem considers a more general and more complex version of Problem 30 where some symbols are unknown and some others are fixed constant symbols. Searching texts for a fixed pattern is rather restrictive in some contexts, and parameterised string matching provides an efficient solution in several applications by introducing variables in patterns. The problem was initially stated to detect code duplicates in which, for example, identifiers are substituted for the original names.

Let $\A$ and $\varA$ be two disjoint alphabets: $\A$ is the alphabet of constant letters and $\varA$ is the alphabet of variable letters. We assume that no alphabet contains integers. A word over $\A\cup\varA$ is called a parameterised word or a p-word. Two p-words $x$ and $y$ are said to match or p-match if $x$ can be transformed into $y$ by applying a one-to-one mapping on symbols of $\varA$ occurring in $x$.

The parameterised pattern matching problem can be stated as follows: given a pattern $x\in (\A\cup\varA)^*$ and a text $y\in(\A\cup\varA)^*$ find all the p-occurrences of $x$ in $y$, that is, find all the positions $j$ on $y$, $0\le j \le |y|-|x|$, for which $x$ and $y[j \dd j+|x|-1]$ p-match.

Design an algorithm that solves the parameterised pattern matching problem and runs in linear time for a fixed alphabet.

References

  • A. Amir, M. Farach, and S. Muthukrishnan. Alphabet dependence in parameterized matching. Inf. Process. Lett., 49(3):111-115, 1994.
  • B. S. Baker. A theory of parameterized pattern matching: algorithms and applications. In S. R. Kosaraju, D. S. Johnson, and A. Aggarwal, editors, Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pages 71-80. ACM, 1993.
  • B. S. Baker. Parameterized pattern matching: Algorithms and applications. J. Comput. Syst. Sci., 52(1):28-42, 1996.
  • R. M. Idury and A. A. Schäffer. Multiple matching of parameterized patterns. Theor. Comput. Sci., 154(2):203-224, 1996.
  • J. Mendivelso and Y. Pinzón. Parameterized matching: Solutions and extensions. In J. Holub and J. Zdárek, editors, Proceedings of the Prague Stringology Conference 2015, pages 118-131, Czech Technical University in Prague, Czech Republic, 2015.