Export

Link to this page

Please use this URL for citations.

Search Other Services

Statistics

  • Access to this page：2,643 times

＜conference paper＞
A Note on Randomized Algorithm for String Matching with Mismatches

Creator
Creator Name
Baba, Kensuke
馬場, 謙介
ババ, ケンスケ
Affiliation
Affiliation Name
Faculty of Information Science and Electrical Engineering, Kyushu University
九州大学システム情報科学研究院
Author PID
K000166
Creator Name
Shinohara, Ayumi
篠原, 歩
シノハラ, アユミ
Affiliation
Affiliation Name
Faculty of Information Science and Electrical Engineering, Kyushu University
九州大学システム情報科学研究院>
Author PID
K000172
Creator Name
Takeda, Masayuki
竹田, 正幸
タケダ, マサユキ
Affiliation
Affiliation Name
Faculty of Information Science and Electrical Engineering, Kyushu University
九州大学システム情報科学研究院
Author PID
K003385
Creator Name
Inenaga, Shunsuke
稲永, 俊介
イネナガ, シュンスケ
Affiliation
Affiliation Name
Faculty of Information Science and Electrical Engineering, Kyushu University
九州大学システム情報科学研究院
Author PID
K000164
Creator Name
Arikawa, Setsuo
有川, 節夫
アリカワ, セツオ
Affiliation
Affiliation Name
Faculty of Information Science and Electrical Engineering, Kyushu University
九州大学システム情報科学研究院
Language
English
Publisher
Czech Technical University
Date
2002-09
Source Title
Proceedings of the Prague Stringology Conference
Vol
2002
First Page
9
Last Page
17
Publication Type
Accepted Manuscript
Access Rights
open access
Related DOI
Proceedings of the Prague Stringology Conference || 2002 || p9-17
http://www.stringology.org/
Related URI
Proceedings of the Prague Stringology Conference || 2002 || p9-17
http://www.stringology.org/
Relation
Proceedings of the Prague Stringology Conference || 2002 || p9-17
http://www.stringology.org/
Abstract Atallah et al. [2] introduced a randomized algorithm for string matching with mismatches, which utilized fast Fourier transformation (FFT) to compute convolution. It estimates the score vector of matc...hes between text string and a pattern string, that is, the vector obtained when the pattern is slid along the text, and the number of matches is counted for each position. This paper simplifies the algorithm and give an exact analysis of the variance of the estimator.show more

Hide fulltext details.

pdf BSTIA02 pdf 170 KB 255  

Details

Record ID
15557
Peer-Reviewed
Refereed
Subject Terms
pattern matching
mismatch
FFT
convolution
randomized algorithm
Notes
Prague Stringology Conference '02 (PSC '02) : September 23-24, 2002 : Czech Technical University in Prague
Created Date 2009.10.15
Modified Date 2020.12.08

People who viewed this item also viewed