Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW

Re: "Inverse" Pattern Matching

by choroba (Chancellor)
on Jul 04, 2013 at 22:32 UTC ( #1042533=note: print w/replies, xml ) Need Help??

in reply to "Inverse" Pattern Matching

What about this? I keep a list of possible positions, I delete non-matching positions recursively character by character. If I make the string much longer (x 100_000), it still runs only for 8 seconds on my box.
#!/usr/bin/perl use warnings; use strict; use feature qw(say); # 1 2 3 4 # 0123456789012345678901234567890123456789012345 # | | | | | | our $string = '1234561234123x561234123x61234x3456123412345x1'; our $pattern = '123456'; our $pattern_length = length $pattern; our %results; search(0, 0, [0 .. length($string) - 1]); say for sort { $a <=> $b } keys %results; sub search { my ($p_pos, $s_pos, $positions) = @_; return if $p_pos > $pattern_length; return unless @$positions; if ($p_pos == $pattern_length) { undef @results{@$positions}; return; } my $char = substr $pattern, $p_pos, 1; search($p_pos + 1, $s_pos + 1, [ grep { my $ch = substr($string, $s_pos + $_, 1); $char eq $ch or 'x' eq $ch; } @$positions ]); search($p_pos + 2, $s_pos + 1, [ grep substr($string, $s_pos + $_, 1) eq 'x', @$positions ]); }
لսႽ ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ

Replies are listed 'Best First'.
Re^2: "Inverse" Pattern Matching
by hdb (Prior) on Jul 05, 2013 at 12:21 UTC

    Thanks a lot. I am still working to get a proper understanding but your proposal has already found a match in my example that I have overlooked!

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1042533]
[davido]: I'll look into it in a few hours probably.
[davido]: when i do get to that point I think I'll do it in a vm snapshot just in case. :)
[oiskuu]: tye, you were right: loginuid/sessionid are part of task struct if compiled with AUDITSYSCALL. I have some doubts if you should actually depend on that feature.
[Corion]: oiskuu: Depends on what you want to do with that information
[tye]: I'm not depending on that feature. But I could in this environment. I'm using getlogin(). shrug
[Corion]: For benign logging (which user started this DB instance), it's OK
[tye]: We use auditd for security monitoring. So we can rely on auditing being enabled. I'm not sure who would want to not be able to audit. Maybe some VM inside another system with audit?
[SuicideJunkie]: spies would want a system to not be able to audit.

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (7)
As of 2017-06-23 20:12 GMT
Find Nodes?
    Voting Booth?
    How many monitors do you use while coding?

    Results (555 votes). Check out past polls.