Το IndexOf θα επιστρέψει 4 φορές, οι άλλες λύσεις και ένα απλό regex (χωρίς lookback) θα επιστρέψουν 2. Το θέμα είναι κατά πόσο θεωρείται αποδεκτό από το context τα αποτελέσματα να αναφέρονται σε επικαλυπτόμενα strings.

---

Μην αφήνετε τα media να σας "ταΐζουν"!

Το τί θα επιστρέψει ο κάθε τρόπος αλλάζει εύκολα όπως έδειξε και ο anjelinio. Όλες οι περιπτώσεις μπορούν να δώσουν είτε 2 είτε 4 ως αποτέλεσμα.

---

Παναγιώτης Καναβός, Freelancer
Twitter: http://www.twitter.com/pkanavos

Χμ... ελπίζω να μην είναι κάτι προφανές που αγνοώ, αλλά δεν βλέπω πώς θα μπορούσε η λύση με το replace ή το Split() να επιστρέψει 4 στο παράδειγμα με το "NNN" string του Νίκου, τουλάχιστον όπως το κοιτάω τώρα, μετά από 36 ώρες αϋπνίας + δουλειάς.

---

Μην αφήνετε τα media να σας "ταΐζουν"!

Αυτές τις απορρίψαμε πριν από 10 posts!

---

Παναγιώτης Καναβός, Freelancer
Twitter: http://www.twitter.com/pkanavos

Ορίστε και η δική μου έκδοση, καταρχήν ως substr_count, για να τιμήσουμε την PHP που έχει αυτό το function:

static int substr_count(string haystack, string needle,bool countOverlaps)
{
   int startIndex=0,counter=0;
   int needleLength = countOverlaps ? 1 : needle.Length;
   while ((startIndex= haystack.IndexOf(needle, startIndex)+needleLength) >= needleLength)
      counter++;
   return counter;
}

και ως extension method στην String, για να γράφουμε "NNNNNN".SubstringCount("NN",true)==3!

public static class StringExtensions
{
   public static int SubstringCount(this string haystack, string needle, bool countOverlaps)
   {
      int startIndex = 0, counter = 0;
      int needleLength = countOverlaps ? 1 : needle.Length;
      while ((startIndex = haystack.IndexOf(needle, startIndex) + needleLength) >= needleLength)
         counter++;
      return counter;
   }
}

Ουσιαστικά, η position που είχε βάλει ο Palladin έφυγε και αντί γι αυτή ανανεώνεται απευθείας η startIndex. Αν δεν βρεθεί ένα substring, το αποτέλεσμα της IndexOf θα είναι αρνητικό οπότε το άθροισμα του αποτελέσματος + το μήκος της λέξης θα είναι μικρότερα από το μήκος της λέξης. Μπήκα στον πειρασμό να βάλω και τον ορισμό της needleLength στην πρώτη γραμμή, αλλά είπα να δείξω χαρακτήρα!

---

Παναγιώτης Καναβός, Freelancer
Twitter: http://www.twitter.com/pkanavos

Βρήκα και αυτά τα αρθράκια στο Wikipedia για Suffix trees και Suffix arrays, τα οποία χρησιμοποιούνται για να επιταχύνουν αναζητήσεις και substring counts σε ΜΕΓΑΛΑ strings. Ουσιαστικά, δημιουργείται από το αρχικό string ένα δέντρο ή ένα sorted array με όλα τα substrings, από το τέλος προς την αρχή. Για το string "abracadabra" ένα suffix array θα περιέχει τα παρακάτω strings:

a
abra
abracadabra
acadabra
adabra
bra
bracadabra
cadabra
dabra
ra
racadabra

Μετά είναι εύκολο να βρει κανείς ένα συγκεκριμένο suffix με binary search. Για να βρεί κανείς το substring count μετράει πόσα suffixes ξεκινάνε με το συγκεκριμένο substring. Χρησιμοποιώντας τα καλούδια του .NET η υλοποίηση γίνεται :

public static class SuffixExtensions
{
   public static int CountSubstring(this List<string> list, string needle) 
   {
      int startIndex = list.BinarySearch(needle);
      //If no exact match is found, the bitwise complement of the index is the first string greater than the needle, 
      //ie. the first string that starts with the needle
      startIndex = startIndex >= 0 ? startIndex : ~startIndex;

      int count = 0;
      for (int j = startIndex; j < list.Count; j++)
      {
         if (list[j].StartsWith(needle))
            count++;
         else
            return count;
      }
      return count;
   }

   public static List<string> CreateSuffixArray(this string haystack)
   {
      List<string> list = new List<string>();
      for (int i = 0; i < haystack.Length; i++)
      {
         list.Add(haystack.Substring(i));
      }
      list.Sort();
      return list;
   }
}

Έτσι το substring count γίνεται ως εξής:

List<string> list = "abracadabrabra".CreateSuffixArray();
int count = list.CountSubstring("ra");

το οποίο θα γυρίσει 3. Η υλοποίηση αυτή επιστρέφει και τα overlapping substrings. Η δημιουργία του suffix array κοστίζει αλλά οι αναζητήσεις γίνονται πολύ γρήγορες. Αν θέλει κανείς να κάνει πολλές αναζητήσεις στο ίδιο κείμενο η ταχύτητα αυξάνεται σημαντικά.

---

Παναγιώτης Καναβός, Freelancer
Twitter: http://www.twitter.com/pkanavos

Είσαι λίγο μνημοβόρος όμως. Χρειάζεσαι n(n+1)/2 ενδιάμεσα strings, ή κάνω λάθος;

---

Μην αφήνετε τα media να σας "ταΐζουν"!

Όχι, μόνο N strings αλλά n(n+1) chars καθώς χρησιμοποιούνται οι καταλήξεις κι όχι όλα τα δυνατά substrings. Στόχος δεν είναι η ελάχιστη μνήμη αλλά η μέγιστη ταχύτητα. Γι αυτό και είπα ότι είναι για μεγάλα strings και αλλεπάλληλες αναζητήσεις. Για μία αναζήτηση μόνο είναι εντελώς περιττό. Αν όμως θέλει κανείς να ψάξει επανηλλημένα για ένα substring η αναζήτηση είναι ένα πολύ γρήγορο binary search.  Η γραμμική αναζήτηση έχει πολυπλοκότητα Ο(m+n) όπου m το μέγεθος του substring και n το μέγεθος του μεγάλου string. Η πολυπλοκότητα του binary search είναι O(m*logn). Αν το substring είναι μικρό σε σχέση με το αρχικό string η διαφορά ταχύτητας είναι σημαντική. Ψάχνοντας για ένα substring των 10 χαρακτήρων σε ένα string των 1000 χαρακτήρων θα δώσει στην πρώτη περίπτωση 1010 ενώ στη δεύτερη 30. Και μετά πολλαπλασιάζουμε το νούμερο με τον αριθμό queries που θέλουμε να κάνουμε.

 Το ίδιο πράγμα συμβαίνει με οποιαδήποτε δομή η οποία χρησιμοποιείται για indexing, παίρνουν συνήθως πολύ περισσότερη μνήμη αλλά επιταχύνουν τόσο πολύ τις αναζητήσεις ώστε το κόστος της δημιουργίας του index θεωρείται ότι μοιράζεται και είναι αμελητέο. Αν η πληροφορία που αναζητούμε είναι μικρή σε σχέση με το συνολικό όγκο πληροφορίας, ένα index επιταχύνει τη διαδικασία. Διαφορετικά είναι καλύτερη η γραμμική αναζήτηση. Αυτό γίνεται και με τον SQL Server, όταν κάποιες φορές επιλέγει να κάνει table scan αντί να χρησιμοποιήσει κάποιο index.

Τον κώδικα που έγραψα τον ψιλοέκλεψα από ένα απλό implementation σε Ruby με τη διαφορά ότι χρησιμοποίησα τα έτοιμα functions του .ΝΕΤ. H List<T>.Sort() χρησιμοποιεί QuickSort οπότε δεν είχα τις ανησυχίες του αρθρογράφου για το Enumerable#sort της Ruby, ενώ το BinarySearch ήταν κι αυτό έτοιμο. Η γραμμική αναζήτηση μετά για να βρώ όλα τα substrings που ξεκινούν με το substring που ψάχνω είναι λίγο χαζή, αλλά βαρέθηκα να ψάξω και για κάποιο καλύτερο αλγόριθμο!

Η ταχύτητα, ειδικά για το substring count, μπορεί να βελτιωθεί αρκετά αν χρησιμοποιηθούν suffix trees, στην οποία περίπτωση το substring count είναι ο αριθμός των πεδιών του πρώτου κόμβου που ξεκινάει με το substring που ψάχνουμε. Αυτός ο υπολογισμός μπορεί να γίνει άνετα τη στιγμή που δημιουργείται ένα δέντρο οπότε η αναζήτηση για ένα substring μπορεί να γίνει απλά O(logn). Βρήκα μία υλοποίηση σε C++ στο http://blog.lizhao.net/2005/01/c-implementation-of-ukkonens-suffix.html η οποία φτιάχνει το δέντρο σε Ο(n) αλλά ... κάτι δεν πήγε καλά στη μετατροπή σε C# και το δέντρο που παίρνω είναι λίγο μυστήριο.

Τα suffix trees και τα suffix arrays δημιουργούνται για να επιταχύνουν πολλαπλά queries π.χ. σε εφαρμογές βιοπληροφορικής όπου μπορεί να έχεις πολύ μεγάλα strings που αντιπροσωπεύουν γονίδια και ψάχνεις να βρεις μία συγκεκριμένη αλληλλουχία δηλαδή ... ένα substring. Επίσης χρησιμοποιούνται από ... προγράμματα antivirus για να ψάξουν για κάποια substrings μέσα σε προγράμματα ή τη μνήμη και τέλος σε μηχανής αναζήτησης. Αλήθεια, ο Δημήτρης τί θέλει να το κάνει?

 

---

Παναγιώτης Καναβός, Freelancer
Twitter: http://www.twitter.com/pkanavos

Ενδιαφέρον. Thumbs up!

---

Μην αφήνετε τα media να σας "ταΐζουν"!