Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Generalised Matching

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 5721))

  • 1151Accesses

Abstract

Given a patternp over an alphabet Σp and a textt over an alphabet Σt, we consider the problem of determining a mappingf from Σp to\({\Sigma}_{t}^{+}\) such thatt = f(p1)f(p2)...f(pm). This class of problems, which was first introduced by Amir and Nor in 2004, is defined by different constraints on the mappingf. We give NP-Completeness results for a wide range of conditions. These include whenf is either many-to-one or one-to-one, when Σt is binary and when the range off is limited to strings of constant length. We then introduce a related problem we termpattern matching with string classes which we show to be solvable efficiently. Finally, we discuss an optimisation variant of generalised matching and give a polynomial-time min\((1,\sqrt{k/OPT})\)-approximation algorithm for fixedk.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Amir, A., Aumann, A., Cole, R., Lewenstein, M., Porat, E.: Function matching: Algorithms, applications, and a lower bound. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 929–942. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  2. Amir, A., Nor, I.: Generalized function matching. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol. 3341, pp. 41–52. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  3. Amir, A., Nor, I.: Generalized function matching. Journal of Discrete Algorithms 5(3), 514–523 (2007)

    Article MathSciNet MATH  Google Scholar 

  4. Baker, B.S.: A theory of parameterized pattern matching: algorithms and applications. In: Proceedings of the 25th Annual ACM Symposium on the Theory of Computing (STOC), pp. 71–80 (1993)

    Google Scholar 

  5. Linhart, C., Shamir, R.: Faster pattern matching with character classes using prime number encoding. Journal of Computer and System Sciences 75(3), 155–162 (2009)

    Article MathSciNet MATH  Google Scholar 

  6. Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing (STOC), pp. 216–226. ACM Press, New York (1978)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Bristol, UK

    Raphael Clifford, Alexandru Popa & Benjamin Sach

  2. Department of Mathematics, University of Bristol, UK

    Aram W. Harrow

Authors
  1. Raphael Clifford

    You can also search for this author inPubMed Google Scholar

  2. Aram W. Harrow

    You can also search for this author inPubMed Google Scholar

  3. Alexandru Popa

    You can also search for this author inPubMed Google Scholar

  4. Benjamin Sach

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Swedish Institute of Computer Science, Kista, Sweden

    Jussi Karlgren

  2. Department of Computer Science and Engineering, Helsinki University of Technology, P.O. Box 5400, 02015 HUT, Espoo, Finland

    Jorma Tarhio

  3. Department of Computer Sciences, University of Tampere, Tampere, Finland

    Heikki Hyyrö

Rights and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Clifford, R., Harrow, A.W., Popa, A., Sach, B. (2009). Generalised Matching. In: Karlgren, J., Tarhio, J., Hyyrö, H. (eds) String Processing and Information Retrieval. SPIRE 2009. Lecture Notes in Computer Science, vol 5721. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03784-9_29

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp