Comment puis-je trouver toutes les positions d'une sous-chaîne dans une chaîne?

Comment pourrais-je aller à ce sujet?Je recherche une chaîne de grande taille pour tous les emplacements d'une chaîne.

source d'informationauteur Herr Char

  1. 11

    Deux autres réponses sont correctes, mais ils sont très lents et avoir O(N^2) complexité. Mais il y a Knuth-Morris-Pratt algorithme qui trouve toutes les sous-chaînes en O(N) la complexité.

    edit:

    Il y a aussi un autre algorithme appelé "Z" avec O(N) la complexité, mais je ne pouvais pas trouver source en anglais de cet algorithme (peut-être parce qu'il est aussi un des plus célèbre chose avec le même nom - le Z-fonction de Riman), donc va juste mettre le code ici et d'expliquer ce qu'il n'.

    void calc_z (string &s, vector<int> & z)
{
    int len = s.size();
    z.resize (len);

    int l = 0, r = 0;
    for (int i=1; i<len; ++i)
        if (z[i-l]+i <= r)
            z[i] = z[i-l];
        else
        {
            l = i;
            if (i > r) r = i;
            for (z[i] = r-i; r<len; ++r, ++z[i])
                if (s[r] != s[z[i]])
                    break;
            --r;
        }
}
int main()
{
    string main_string = "some string where we want to find substring or sub of string or just sub";
    string substring = "sub";
    string working_string = substring + main_string;
    vector<int> z;
    calc_z(working_string, z);

    //after this z[i] is maximal length of prefix of working_string
    //which is equal to string which starting from i-th position of
    //working_string. So the positions where z[i] >= substring.size()
    //are positions of substrings.

    for(int i = substring.size(); i < working_string.size(); ++i)
        if(z[i] >=substring.size())
            cout << i - substring.size() << endl; //to get position in main_string
}
  2. 13

    À l'aide de std::string::find. Vous pouvez faire quelque chose comme:

    std::string::size_type start_pos = 0;
while( std::string::npos != 
          ( start_pos = mystring.find( my_sub_string, start_pos ) ) )
{
    //do something with start_pos or store it in a container
    ++start_pos;
}

    MODIFIER: Doh! Merci pour la remarque, Nawaz! Mieux?

  3. 3

    Je vais ajouter pour être complet, il existe une autre approche est possible avec std::searchfonctionne comme std::string::findla différence est que vous travaillez avec des itérateurs, quelque chose comme:

    std::string::iterator it(str.begin()), end(str.end());
std::string::iterator s_it(search_str.begin()), s_end(search_str.end());

it = std::search(it, end, s_it, s_end);

while(it != end)
{
  //do something with this position..

  //a tiny optimisation could be to buffer the result of the std::distance - heyho..
  it = std::search(std::advance(it, std::distance(s_it, s_end)), end, s_it, s_end);
}

    Je trouve que ce parfois surpasse std::string::findesp. si vous déclarez votre chaîne comme un vector<char>.

  4. 2

    Simplement use std::string::find() qui retourne la position à laquelle la chaîne a été trouvée, ou std::string::npos si aucune n'a été trouvé.

    Ici est la documentation.

    Un ici est l'exemple pris dans cette documentation:

    //string::find
#include <iostream>
#include <string>
using namespace std;

int main ()
{
  string str ("There are two needles in this haystack with needles.");
  string str2 ("needle");
  size_t found;

  //different member versions of find in the same order as above:
  found=str.find(str2);
  if (found!=string::npos)
    cout << "first 'needle' found at: " << int(found) << endl;

  found=str.find("needles are small",found+1,6);
  if (found!=string::npos)
    cout << "second 'needle' found at: " << int(found) << endl;

  found=str.find("haystack");
  if (found!=string::npos)
    cout << "'haystack' also found at: " << int(found) << endl;

  found=str.find('.');
  if (found!=string::npos)
    cout << "Period found at: " << int(found) << endl;

  //let's replace the first needle:
  str.replace(str.find(str2),str2.length(),"preposition");
  cout << str << endl;

  return 0;
}