मैं पर्ल में ओवरलैपिंग सबस्ट्रिंग कैसे गिन सकता हूं?

Question

मुझे पर्ल में एक स्ट्रिंग में एक सबस्ट्रिंग की घटना को गिनने के लिए एक प्रोग्राम को लागू करने की आवश्यकता है। मैंने इसे

sub countnmstr 
{ 
    $count =0; 
    $count++ while $_[0] =~ /$_[1]/g; 
    return $count; 
} 

$count = countnmstr("aaa","aa"); 

print "$count\n"; 

अब यह सामान्य रूप से किया गया है। हालांकि, उपरोक्त कार्यान्वयन में मैं 'aa' में 'aa' की घटना को गिनना चाहता हूं। यहां मुझे 1 के रूप में उत्तर मिलता है जो उचित लगता है लेकिन मुझे ओवरलैपिंग मामलों पर भी विचार करने की आवश्यकता है। इसलिए उपर्युक्त मामले को 2 के रूप में जवाब देना चाहिए क्योंकि अगर हम ओवरलैप मानते हैं तो दो 'एए' हैं।

क्या कोई सुझाव दे सकता है कि इस तरह के फ़ंक्शन को कैसे कार्यान्वित किया जाए ??

Answer 1

ysth's answer देखें ... मुझे यह एहसास हुआ कि पैटर्न पूरी तरह से शून्य चौड़ाई के दावे में शामिल हो सकता है और अभी भी इस उद्देश्य के लिए काम कर सकता है।

आप positive lookahead उपयोग कर सकते हैं के रूप में दूसरों ने सुझाव दिया है, और समारोह के रूप में लिखें:

#!/usr/bin/perl 

use strict; use warnings; 

sub countnmstr { 
    my ($haystack, $needle) = @_; 
    my $adj = length($needle) - 1; 
    die "Search string cannot be empty!" if $adj < 0; 

    my $count = 0; 
    while ($haystack =~ /\Q$needle/g) { 
     pos $haystack -= $adj; 
     $count += 1; 
    } 
    return $count; 
} 

print countnmstr("aaa","aa"), "\n"; 

आउटपुट:

sub countnmstr { 
    my ($haystack, $needle) = @_; 
    my ($first, $rest) = $needle =~ /^(.)(.*)$/; 
    return scalar (() = $haystack =~ /(\Q$first\E(?=\Q$rest\E))/g); 
} 

तुम भी pos उपयोग कर सकते हैं समायोजित करने के लिए जहां अगले खोज से ऊपर उठाता है:

 
C:\Temp> t 
2 

Answer 2

आपका उपयोग कर सकते हैं नियमित अभिव्यक्ति में:

sub countnmstr { 
    my @matches = $_[0] =~ /(?=($_[1]))/g; 

    return scalar @matches; 
} 

मुझे लगता है सिनान के सुझाव जल्दी हालांकि हो जाएगा।

Answer 3

आप इसे आजमा सकते हैं, आवश्यकता से अधिक रेगेक्स नहीं।

$haystack="aaaaabbbcc"; 
$needle = "aa"; 
while (1){ 
    $ind = index($haystack,$needle); 
    if ($ind == -1) {last}; 
    $haystack = substr($haystack,$ind+1); 
    $count++; 
} 
print "Total count: $count\n"; 

उत्पादन

$ ./perl.pl 
Total count: 4 

Answer 4

हर कोई उनके जवाब में बहुत जटिल हो रही है (डी 'ओह! Daotoad उसकी टिप्पणी एक जवाब करना चाहिए था!), शायद इसलिए कि वे goatse ऑपरेटर से डरते हैं। मैंने इसका नाम नहीं दिया, यही वही है जो लोग इसे कहते हैं। यह चाल का उपयोग करता है कि सूची असाइनमेंट का परिणाम राइथेंड सूची में तत्वों की संख्या है।

मैचों की गिनती के लिए पर्ल मुहावरा तो है:

my $count =() = $_[0] =~ /($pattern)/g; 

goatse हिस्सा =() = है, जो दो कार्य के बीच में एक खाली सूची है। बकरी के लम्बे हिस्से को बकरी के ऊपरी हिस्से से गिनती मिलती है। ध्यान दें कि आपको पैटर्न में कैप्चर की आवश्यकता है क्योंकि वह सूची है जो सूची ऑपरेटर सूची संदर्भ में वापस आ जाएगी।

अब, आपके मामले में अगली चाल यह है कि आप वास्तव में एक सकारात्मक दिखना चाहते हैं (या शायद देखो)। lookarounds पात्रों का उपभोग नहीं करते हैं, तो आप स्थिति का ट्रैक रखने की जरूरत नहीं है:

my $count =() = 'aaa' =~ /((?<=a)a)/g; 

आपका aaa सिर्फ एक उदाहरण है। यदि आपके पास एक चर-चौड़ाई पैटर्न है, तो आपको एक लुकहेड का उपयोग करना होगा। पर्ल में लुकबींड्स को चौड़ाई तय करनी होगी।

Answer 5

sub countnmstr 
{ 
    my ($string, $substr) = @_; 
    return scalar(() = $string =~ /(?=\Q$substr\E)/g); 
} 

$count = countnmstr("aaa","aa"); 

print "$count\n"; 

कुछ अंक:

//g सूची संदर्भ में संभव के रूप में कई बार मेल खाता है।

\Q...\E किसी भी मेटा वर्णों को स्वतः से बचने के लिए उपयोग किया जाता है, ताकि आप एक सबस्ट्रिंग गिनती न हो, एक सबस्ट्रिंग गिनती न करें।

एक लुकहेड (?= ...) का उपयोग करके प्रत्येक मैच स्ट्रिंग का "उपभोग" नहीं करता है, जिससे अगले मैच में निम्नलिखित मैच का प्रयास किया जा सकता है।

यह वही सुविधा का उपयोग करता है जहां स्केलर संदर्भ में एक सूची असाइनमेंट (इस मामले में, एक खाली सूची में) सूची असाइनमेंट के दाईं ओर तत्वों की गिनती बकरी/उड़ान-दाल/फैल-ईगल/जो भी ऑपरेटर है, लेकिन स्केलर संदर्भ प्रदान करने के लिए स्केलर असाइनमेंट के बजाय स्केलर() का उपयोग करता है।

$_[0] सीधे उपयोग नहीं किया जाता है, लेकिन इसकी बजाय एक व्याख्यात्मक में प्रतिलिपि बनाई गई है; $string के स्थान पर $_[0] का एक बेवकूफ उपयोग //g को शुरुआती स्ट्रिंग के माध्यम से स्ट्रिंग के माध्यम से भाग शुरू करने के लिए संग्रहीत करने के कारण होगा।

अद्यतन: रों /// जी, तेजी से होता है, हालांकि के रूप में तेजी से नहीं सूचकांक का उपयोग कर के रूप में:

sub countnmstr 
{ 
    my ($string, $substr) = @_; 
    return scalar($string =~ s/(?=\Q$substr\E)//g); 
} 

Answer 6

अगर गति एक मुद्दा है, index दृष्टिकोण (सीजेएम के सुधार के साथ) ghostdog74 ने सुझाव दिया है होने की संभावना है रेगेक्स समाधान से काफी तेज है।

use strict; 
use warnings; 

sub countnmstr_regex { 
    my ($haystack, $needle) = @_; 
    return scalar(() = $haystack =~ /(?=\Q$needle\E)/g); 
} 

sub countnmstr_index { 
    my ($haystack, $needle) = @_; 
    my $i = 0; 
    my $tally = 0; 
    while (1){ 
     $i = index($haystack, $needle, $i); 
     last if $i == -1; 
     $tally ++; 
     $i ++; 
    } 
    return $tally; 
} 

use Benchmark qw(cmpthese); 

my $size = 1; 
my $h = 'aaa aaaaaa' x $size; 
my $n = 'aa'; 

cmpthese(-2, { 
    countnmstr_regex => sub { countnmstr_regex($h, $n) }, 
    countnmstr_index => sub { countnmstr_index($h, $n) }, 
}); 

__END__ 

# Benchmarks run on Windows. 
# Result using a small haystack ($size = 1). 
        Rate countnmstr_regex countnmstr_index 
countnmstr_regex 93701/s    --    -66% 
countnmstr_index 271893/s    190%    -- 

# Result using a large haystack ($size = 100). 
        Rate countnmstr_regex countnmstr_index 
countnmstr_regex 929/s    --    -81% 
countnmstr_index 4960/s    434%    --