Znajdowanie wszystkich pozycji podciągu w większym ciągu w C #

83

Mam duży ciąg, który muszę przeanalizować, i muszę znaleźć wszystkie wystąpienia extract"(me,i-have lots. of]punctuationi zapisać indeks każdego z nich na liście.

Powiedzmy więc, że ten fragment łańcucha znajdował się na początku i w środku większego ciągu, oba zostaną znalezione, a ich indeksy zostaną dodane do List. a Listbędzie zawierać 0i inny indeks, cokolwiek by to było.

Bawiłem się, a string.IndexOfrobi prawie to, czego szukam, i napisałem trochę kodu - ale to nie działa i nie byłem w stanie dowiedzieć się, co jest nie tak:

List<int> inst = new List<int>();
int index = 0;
while (index < source.LastIndexOf("extract\"(me,i-have lots. of]punctuation", 0) + 39)
{
    int src = source.IndexOf("extract\"(me,i-have lots. of]punctuation", index);
    inst.Add(src);
    index = src + 40;
}
  • inst = Lista
  • source = Duży ciąg

Jakieś lepsze pomysły?

c#  .net  asp.net  string 
— Caesay
źródło

Odpowiedzi:

142

Oto przykładowa metoda rozszerzenia:

public static List<int> AllIndexesOf(this string str, string value) {
    if (String.IsNullOrEmpty(value))
        throw new ArgumentException("the string to find may not be empty", "value");
    List<int> indexes = new List<int>();
    for (int index = 0;; index += value.Length) {
        index = str.IndexOf(value, index);
        if (index == -1)
            return indexes;
        indexes.Add(index);
    }
}

Jeśli umieścisz to w klasie statycznej i zaimportujesz przestrzeń nazw za pomocą using, pojawi się jako metoda na dowolnym łańcuchu i możesz po prostu zrobić:

List<int> indexes = "fooStringfooBar".AllIndexesOf("foo");

Więcej informacji na temat metod rozszerzeń można znaleźć pod adresem http://msdn.microsoft.com/en-us/library/bb383977.aspx

To samo z użyciem iteratora:

public static IEnumerable<int> AllIndexesOf(this string str, string value) {
    if (String.IsNullOrEmpty(value))
        throw new ArgumentException("the string to find may not be empty", "value");
    for (int index = 0;; index += value.Length) {
        index = str.IndexOf(value, index);
        if (index == -1)
            break;
        yield return index;
    }
}
— Matti Virkkunen
źródło
8
Dlaczego nie używać IEnumerable <int> i zwracanego indeksu zwrotu zamiast listy indeksów?
— m0sa
2
@ m0sa: Słuszna uwaga. Dodano kolejną wersję tylko dla zabawy.
— Matti Virkkunen
2
@ PedroC88: Użycie yieldspowoduje, że kod będzie „leniwy”. Nie zbierze wszystkich indeksów na liście w pamięci w ramach metody. Jaki praktyczny wpływ ma to na wydajność, zależy od wielu czynników.
— Matti Virkkunen
1
@Paul: „Nie wolno” jak w „nie wolno”. Jeśli nie podoba ci się sformułowanie, zawsze możesz zasugerować zmianę, ale nie sądzę, aby było to trudne do zrozumienia.
— Matti Virkkunen
10
Uwaga! Ze względu na dodawanie value.Lengthmożesz przegapić zagnieżdżone dopasowania! Przykład: „To jest test dopasowania zagnieżdżonego!” z dopasowaniem do „NestedNested” zostanie znaleziony tylko jeden indeks, ale nie zagnieżdżony. Aby to naprawić, po prostu dodaj +=1pętlę zamiast +=value.Length.
— Christoph Meißner
20

Dlaczego nie używasz wbudowanej klasy RegEx:

public static IEnumerable<int> GetAllIndexes(this string source, string matchString)
{
   matchString = Regex.Escape(matchString);
   foreach (Match match in Regex.Matches(source, matchString))
   {
      yield return match.Index;
   }
}

Jeśli musisz ponownie użyć wyrażenia, skompiluj je i gdzieś w pamięci podręcznej. Zmień parametr matchString na Regex matchExpression w innym przeciążeniu dla przypadku ponownego użycia.

— csaam
źródło
To się nie kompiluje
— Anshul
co jest indexes? Nigdzie nie jest zdefiniowane.
— Saggio
Moja wina to pozostałość. Usuń tę linię.
— csaam
2
Uważaj, ta metoda ma tę samą wadę, co zaakceptowana odpowiedź. Jeśli ciąg źródłowy to „ccc”, a wzorzec to „cc”, zwróci tylko jedno wystąpienie.
— user280498
15

przy użyciu LINQ 

public static IEnumerable<int> IndexOfAll(this string sourceString, string subString)
{
    return Regex.Matches(sourceString, subString).Cast<Match>().Select(m => m.Index);
}
— ehosca
źródło
2
Zapomniałeś jednak uciec z subString.
— csaam
Jest to lepsze rozwiązanie niż przyjęte rozwiązanie ze względu na mniejszą złożoność cyklomatyczną.
— Denny Jacob
5

Wersja polerowana + obsługa ignorowania wielkości liter:

public static int[] AllIndexesOf(string str, string substr, bool ignoreCase = false)
{
    if (string.IsNullOrWhiteSpace(str) ||
        string.IsNullOrWhiteSpace(substr))
    {
        throw new ArgumentException("String or substring is not specified.");
    }

    var indexes = new List<int>();
    int index = 0;

    while ((index = str.IndexOf(substr, index, ignoreCase ? StringComparison.OrdinalIgnoreCase : StringComparison.Ordinal)) != -1)
    {
        indexes.Add(index++);
    }

    return indexes.ToArray();
}
— net_prog
źródło
2

Można to zrobić w efektywnej złożoności czasowej za pomocą algorytmu KMP w O (N + M), gdzie N to długość, texta M to długość pattern.

Oto implementacja i użycie:

static class StringExtensions
{
    public static IEnumerable<int> AllIndicesOf(this string text, string pattern)
    {
        if (string.IsNullOrEmpty(pattern))
        {
            throw new ArgumentNullException(nameof(pattern));
        }
        return Kmp(text, pattern);
    }

    private static IEnumerable<int> Kmp(string text, string pattern)
    {
        int M = pattern.Length;
        int N = text.Length;

        int[] lps = LongestPrefixSuffix(pattern);
        int i = 0, j = 0; 

        while (i < N)
        {
            if (pattern[j] == text[i])
            {
                j++;
                i++;
            }
            if (j == M)
            {
                yield return i - j;
                j = lps[j - 1];
            }

            else if (i < N && pattern[j] != text[i])
            {
                if (j != 0)
                {
                    j = lps[j - 1];
                }
                else
                {
                    i++;
                }
            }
        }
    }

    private static int[] LongestPrefixSuffix(string pattern)
    {
        int[] lps = new int[pattern.Length];
        int length = 0;
        int i = 1;

        while (i < pattern.Length)
        {
            if (pattern[i] == pattern[length])
            {
                length++;
                lps[i] = length;
                i++;
            }
            else
            {
                if (length != 0)
                {
                    length = lps[length - 1];
                }
                else
                {
                    lps[i] = length;
                    i++;
                }
            }
        }
        return lps;
    }

a to jest przykład jak z niego korzystać:

static void Main(string[] args)
    {
        string text = "this is a test";
        string pattern = "is";
        foreach (var index in text.AllIndicesOf(pattern))
        {
            Console.WriteLine(index); // 2 5
        }
    }
— M.Khooryani
źródło
Jaka jest wydajność tego w porównaniu z optymalną implementacją IndexOf, w której indeks rozpoczęcia wyszukiwania jest ustawiony na koniec poprzedniego dopasowania w każdej iteracji?
— caesay
Porównanie IndexOf z AllIndicesOf jest niepoprawne, ponieważ ich dane wyjściowe są różne. Użycie metody IndexOf w każdej iteracji ogromnie zwiększa złożoność czasową do O (N ^ 2 M), podczas gdy optymalna złożoność wynosi O (N + M). KMP nie działa podobnie do naiwnego podejścia, używa wstępnie obliczonej tablicy (LPS), aby uniknąć wyszukiwania od początku. Polecam przeczytanie algorytmu KMP. Ostatnie akapity sekcji „Tło” w Wikipedii wyjaśniają, jak to działa w języku O (N).
— M.Khooryani,
1 
public List<int> GetPositions(string source, string searchString)
{
    List<int> ret = new List<int>();
    int len = searchString.Length;
    int start = -len;
    while (true)
    {
        start = source.IndexOf(searchString, start + len);
        if (start == -1)
        {
            break;
        }
        else
        {
            ret.Add(start);
        }
    }
    return ret;
}

Nazwij to tak:

List<int> list = GetPositions("bob is a chowder head bob bob sldfjl", "bob");
// list will contain 0, 22, 26
— MusiGenesis
źródło
1

Cześć, dobra odpowiedź od @Matti Virkkunen

public static List<int> AllIndexesOf(this string str, string value) {
    if (String.IsNullOrEmpty(value))
        throw new ArgumentException("the string to find may not be empty", "value");
    List<int> indexes = new List<int>();
    for (int index = 0;; index += value.Length) {
        index = str.IndexOf(value, index);
        if (index == -1)
            return indexes;
        indexes.Add(index);
        index--;
    }
}

Ale to obejmuje przypadki testowe, takie jak AOOAOOA, gdzie podciąg

są AOOA i AOOA

Wyjście 0 i 3

— Pranay Deep
źródło
1

Bez Regex, przy użyciu typu porównania ciągów:

string search = "123aa456AA789bb9991AACAA";
string pattern = "AA";
Enumerable.Range(0, search.Length)
   .Select(index => { return new { Index = index, Length = (index + pattern.Length) > search.Length ? search.Length - index : pattern.Length }; })
   .Where(searchbit => searchbit.Length == pattern.Length && pattern.Equals(search.Substring(searchbit.Index, searchbit.Length),StringComparison.OrdinalIgnoreCase))
   .Select(searchbit => searchbit.Index)

Zwraca to {3,8,19,22}. Pusty wzorzec pasowałby do wszystkich pozycji.

W przypadku wielu wzorów:

string search = "123aa456AA789bb9991AACAA";
string[] patterns = new string[] { "aa", "99" };
patterns.SelectMany(pattern => Enumerable.Range(0, search.Length)
   .Select(index => { return new { Index = index, Length = (index + pattern.Length) > search.Length ? search.Length - index : pattern.Length }; })
   .Where(searchbit => searchbit.Length == pattern.Length && pattern.Equals(search.Substring(searchbit.Index, searchbit.Length), StringComparison.OrdinalIgnoreCase))
   .Select(searchbit => searchbit.Index))

Zwraca to {3, 8, 19, 22, 15, 16}

— Sean
źródło
1

@csam jest poprawny w teorii, chociaż jego kod nie będzie zgodny i można go załamać

public static IEnumerable<int> IndexOfAll(this string sourceString, string matchString)
{
    matchString = Regex.Escape(matchString);
    return from Match match in Regex.Matches(sourceString, matchString) select match.Index;
}
— arame3333
źródło
jeśli jego kod był nieprawidłowy, mogłeś edytować jego post, aby go poprawić
— caesay
Nie zauważyłem tego. Muszę przyznać, że niechętnie to robię, na wypadek, gdyby się mylę, chociaż nie sądzę.
— arame3333
używanie wyrażenia regularnego do dużych łańcuchów nie jest dobrym pomysłem. To podejście wymaga dużo pamięci.
— W92
1

Zauważyłem, że co najmniej dwa proponowane rozwiązania nie obsługują nakładających się wyników wyszukiwania. Nie sprawdziłem tego oznaczonego zielonym haczykiem. Oto taki, który obsługuje nakładające się wyniki wyszukiwania:

    public static List<int> GetPositions(this string source, string searchString)
    {
        List<int> ret = new List<int>();
        int len = searchString.Length;
        int start = -1;
        while (true)
        {
            start = source.IndexOf(searchString, start +1);
            if (start == -1)
            {
                break;
            }
            else
            {
                ret.Add(start);
            }
        }
        return ret;
    }
— Kevin Baker
źródło
0 
public static Dictionary<string, IEnumerable<int>> GetWordsPositions(this string input, string[] Susbtrings)
{
    Dictionary<string, IEnumerable<int>> WordsPositions = new Dictionary<string, IEnumerable<int>>();
    IEnumerable<int> IndexOfAll = null;
    foreach (string st in Susbtrings)
    {
        IndexOfAll = Regex.Matches(input, st).Cast<Match>().Select(m => m.Index);
        WordsPositions.Add(st, IndexOfAll);

    }
    return WordsPositions;
}
— miguel quiros garcia
źródło
-1

W oparciu o kod, którego użyłem do znalezienia wielu wystąpień ciągu w większym ciągu, Twój kod wyglądałby następująco:

List<int> inst = new List<int>();
int index = 0;
while (index >=0)
{
    index = source.IndexOf("extract\"(me,i-have lots. of]punctuation", index);
    inst.Add(index);
    index++;
}
— Corin
źródło
Występują tu dwa problemy: Po pierwsze, zawsze dodajesz -1 do listy wyników, co nie jest prawidłowym wynikiem. Po drugie, kod nie kończy się z powodu indexOfzwrócenia -1 i index++. Użyłbym a while (true)z a, break;jeśli wynik IndexOfjest równy -1.
— b-pos465
-1

Znalazłem ten przykład i umieściłem go w funkcji:

    public static int solution1(int A, int B)
    {
        // Check if A and B are in [0...999,999,999]
        if ( (A >= 0 && A <= 999999999) && (B >= 0 && B <= 999999999))
        {
            if (A == 0 && B == 0)
            {
                return 0;
            }
            // Make sure A < B
            if (A < B)
            {                    
                // Convert A and B to strings
                string a = A.ToString();
                string b = B.ToString();
                int index = 0;

                // See if A is a substring of B
                if (b.Contains(a))
                {
                    // Find index where A is
                    if (b.IndexOf(a) != -1)
                    {                            
                        while ((index = b.IndexOf(a, index)) != -1)
                        {
                            Console.WriteLine(A + " found at position " + index);
                            index++;
                        }
                        Console.ReadLine();
                        return b.IndexOf(a);
                    }
                    else
                        return -1;
                }
                else
                {
                    Console.WriteLine(A + " is not in " + B + ".");
                    Console.ReadLine();

                    return -1;
                }
            }
            else
            {
                Console.WriteLine(A + " must be less than " + B + ".");
               // Console.ReadLine();

                return -1;
            }                
        }
        else
        {
            Console.WriteLine("A or B is out of range.");
            //Console.ReadLine();

            return -1;
        }
    }

    static void Main(string[] args)
    {
        int A = 53, B = 1953786;
        int C = 78, D = 195378678;
        int E = 57, F = 153786;

        solution1(A, B);
        solution1(C, D);
        solution1(E, F);

        Console.WriteLine();
    }

Zwroty:

53 znaleziono na pozycji 2

78 w pozycji 4
78 znalezione w pozycji 7

57 nie ma w 153786

— Znaki
źródło
1
Cześć Mark, widzę, że jesteś nowy w stackoverflow. Ta odpowiedź nic nie dodaje do tego starego pytania, są już o wiele lepsze odpowiedzi. Jeśli w przyszłości będziesz odpowiadać na takie pytanie, spróbuj wyjaśnić, dlaczego Twoja odpowiedź zawiera pewne informacje lub wartości, których nie ma w innych odpowiedziach.
— caesay
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.