|Perl: the Markov chain saw|
Find Prefix if regex didn't matchby demoralizer (Sexton)
|on Oct 31, 2012 at 11:16 UTC||Need Help??|
demoralizer has asked for the
wisdom of the Perl Monks concerning the following question:
I'm "using" perlmonks since years and most of the time I've found good answers for my questions but now I fear I have a quite hard one what made it necessary to create an account and join you :)
Here it is:
I have a given regular expression and a GROWING string to be searched through. All the time the string enlarges I will do a search if the given expression can be machted now. If the string enlarges sign wise (and I don't know when it will become larger next time) and if it is quite large the searching becomes quite slow!
To speed this up the solution I have in mind is cutting the head of the string if it is impossible that the regular expression will be found there. This sounds easy because the string can be cut at that start searching position where the regexp engine reached the end of the string the first time. But I have no idea how I can get this information.
Here a little example:
$string="WWWA" -> we can cat WWW
now string enlarges...
$string="WWWADBBBABC" -> we can cut WWWADBBB
and so on...
Stupid expressions like $search=".*ABC" are quite harder to handle but that's not so important and therefore I will ignore such special cases, just keep it simple what means if the regexp engine reaches end of string while matching use the position where it started search in that case to cut the string.