Window-Accumulated Subsequence Matching Problem is Linear.

@inproceedings{DBLP:conf/pods/BoassonCGM99,
  author    = {Luc Boasson and
               Patrick C{\'e}gielski and
               Ir{\`e}ne Guessarian and
               Yuri Matiyasevich},
  title     = {Window-Accumulated Subsequence Matching Problem is Linear},
  booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,
               Pennsylvania},
  publisher = {ACM Press},
  year      = {1999},
  isbn      = {1-58113-062-7},
  pages     = {327-336},
  ee        = {http://doi.acm.org/10.1145/303976.304008, db/conf/pods/BoassonCGM99.html},
  crossref  = {DBLP:conf/pods/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1999 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD DiSC

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/DISC001 or /cdrom

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[A90]

...

[AHU74]

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6

[BYG92]

Ricardo A. Baeza-Yates, Gaston H. Gonnet: A New Approach to Text Searching. Commun. ACM 35(10): 74-82(1992)

[BYN96]

Ricardo A. Baeza-Yates, Gonzalo Navarro: A Faster Algorithm for Approximate String Matching. CPM 1996: 1-23

[BG95]

Amir M. Ben-Amram, Zvi Galil: On the Power of the Shift Instruction. Inf. Comput. 117(1): 19-36(1995)

[C71]

...

[C88]

Maxime Crochemore: String Matching with Constraints. MFCS 1988: 44-58

[DFGGK97]

Gautam Das, Rudolf Fleischer, Leszek Gasieniec, Dimitrios Gunopulos, Juha Kärkkäinen: Episode Matching. CPM 1997: 12-27

[G81]

Zvi Galil: String Matching in Real Time. J. ACM 28(1): 134-149(1981)

[KMP77]

Donald E. Knuth, James H. Morris Jr., Vaughan R. Pratt: Fast Pattern Matching in Strings. SIAM J. Comput. 6(2): 323-350(1977)

[KR97]

Gregory Kucherov, Michaël Rusinowitch: Matching a Set of Strings with Variable Length don't Cares. Theor. Comput. Sci. 178(1-2): 129-154(1997)

[MBY91]

Udi Manber, Ricardo A. Baeza-Yates: An Algorithm for String Matching with a Sequence of don't Cares. Inf. Process. Lett. 37(3): 133-136(1991)

[M97]

Heikki Mannila: Methods and Problems in Data Mining. ICDT 1997: 41-55

[MTV95]

Heikki Mannila, Hannu Toivonen, A. Inkeri Verkamo: Discovering Frequent Episodes in Sequences. KDD 1995: 210-215

[Ma71]

...

[PRS74]

Vaughan R. Pratt, Michael O. Rabin, Larry J. Stockmeyer: A Characterization of the Power of Vector Machines. STOC 1974: 122-134

[S71]

A. O. Slisenko: String-Matching in Real Time: Some Properties of the Data Structure. MFCS 1978: 493-496

[TRL92]

Jerry L. Trahan, Michael C. Loui, Vijaya Ramachandran: Multiplication, Division and Shift Instructions in Parallel Random Access Machines. Theor. Comput. Sci. 100(1): 1-44(1992)

[U95]

Esko Ukkonen: On-Line Construction of Suffix Trees. Algorithmica 14(3): 249-260(1995)

[WM92]

Sun Wu, Udi Manber: Fast Text Searching Allowing Errors. Commun. ACM 35(10): 83-91(1992)