fjs-string-matching
fjs-string-matching copied to clipboard
CGJennings
How can I make your fjs program suppor "?" searching?
such as finding pattern "a?baa" in text "aabaabaaba bab aaabaa", ? stands for any alphabet,thanks
It is fairly easy to extend the delta array (BMS part) to support indeterminate letters. While just using the BMS part will lose the linear time matching guarantee, it is likely to work fine on almost any real-world data set. Adapting the beta' array (KMP part) is tricky. I refer you to the MSc dissertation by Shu Wang, which discusses your question in detail:
https://macsphere.mcmaster.ca/bitstream/11375/21222/1/Wang_Shu_2005_01_master.pdf
For a more recent overview, see:
Jan Holuba, W.F.Smyth and Shu Wang. Fast pattern-matching on indeterminate strings. Journal of Discrete Algorithms: 6(1): 37-50, 2008.
https://www.sciencedirect.com/science/article/pii/S1570866706000967
It is fairly easy to extend the delta array (BMS part) to support indeterminate letters. While just using the BMS part will lose the linear time matching guarantee, it is likely to work fine on almost any real-world data set. Adapting the beta' array (KMP part) is tricky. I refer you to the MSc dissertation by Shu Wang, which discusses your question in detail:
https://macsphere.mcmaster.ca/bitstream/11375/21222/1/Wang_Shu_2005_01_master.pdf
For a more recent overview, see:
Jan Holuba, W.F.Smyth and Shu Wang. Fast pattern-matching on indeterminate strings. Journal of Discrete Algorithms: 6(1): 37-50, 2008.
https://www.sciencedirect.com/science/article/pii/S1570866706000967
I also think this is a problem; can you give me an example; preferably C/C++
