Pobrać indeks n-tego wystąpienia łańcucha?

101

O ile nie brakuje mi oczywistej wbudowanej metody, jaki jest najszybszy sposób na uzyskanie n- tego wystąpienia ciągu w ciągu?

Zdaję sobie sprawę, że mogę zapętlić metodę IndexOf , aktualizując jej indeks początkowy przy każdej iteracji pętli. Ale robienie tego w ten sposób wydaje mi się marnotrawstwem.

PeteT
źródło
Użyłbym do tego wyrażeń regularnych, a następnie musisz optymalnie dopasować ciąg w ciągu. To w jednym z pięknych DSL, z których wszyscy powinniśmy korzystać, gdy tylko jest to możliwe. Przykład w VB.net kod jest prawie taki sam w C #.
bovium
2
Postawiłbym niezłe pieniądze na wersję z wyrażeniami regularnymi, która jest znacznie trudniejsza do wykonania niż "kontynuowanie zapętlania i robienia prostych String.IndexOf". Wyrażenia regularne mają swoje miejsce, ale nie należy ich używać, gdy istnieją prostsze alternatywy.
Jon Skeet

Odpowiedzi:

52

To w zasadzie to, co musisz zrobić - a przynajmniej jest to najłatwiejsze rozwiązanie. Jedyne, co byś „marnował”, to koszt n wywołań metod - jeśli się nad tym zastanowisz, nie będziesz sprawdzać żadnego przypadku dwa razy. (IndexOf powróci, gdy tylko znajdzie dopasowanie, a ty będziesz kontynuować od miejsca, w którym zostało przerwane).

Jon Skeet
źródło
2
Przypuszczam, że masz rację, ale wygląda na to, że powinna istnieć wbudowana metoda, jestem pewien, że to powszechne zdarzenie.
PeteT
4
Naprawdę? Nie pamiętam, bym kiedykolwiek musiał to robić przez około 13 lat programowania w Javie i C #. To nie znaczy, że nigdy nie musiałem tego robić - ale po prostu nie na tyle często, żeby o tym pamiętać.
Jon Skeet
Mówiąc o Javie, mamy StringUtils.ordinalIndexOf(). C # ze wszystkimi Linq i innymi wspaniałymi funkcjami, po prostu nie ma wbudowanej obsługi tego. I tak, bardzo ważne jest, aby mieć jego wsparcie, jeśli masz do czynienia z parserami i tokenizatorami.
Annie
3
@Annie: Mówisz „mamy” - masz na myśli Apache Commons? Jeśli tak, możesz napisać własną bibliotekę innej firmy dla .NET tak łatwo, jak dla Javy ... więc nie jest tak, że jest to coś, czego biblioteka Javy ma, czego nie ma .NET. I oczywiście w C # można dodać ją jako metodę rozszerzenia na string:)
Jon Skeet
108

Naprawdę możesz użyć wyrażenia regularnego /((s).*?){n}/do wyszukania n-tego wystąpienia podciągu s.

W C # może to wyglądać tak:

public static class StringExtender
{
    public static int NthIndexOf(this string target, string value, int n)
    {
        Match m = Regex.Match(target, "((" + Regex.Escape(value) + ").*?){" + n + "}");

        if (m.Success)
            return m.Groups[2].Captures[n - 1].Index;
        else
            return -1;
    }
}

Uwaga: dodałem Regex.Escapedo oryginalnego rozwiązania, aby umożliwić wyszukiwanie znaków, które mają specjalne znaczenie dla silnika regex.

Alexander Prokofyev
źródło
2
czy powinieneś uciec value? W moim przypadku szukałem kropki msdn.microsoft.com/en-us/library/…
russau
3
Ten Regex nie działa, jeśli ciąg docelowy zawiera podziały wierszy. Czy możesz to naprawić? Dzięki.
Ignacio Soler Garcia
Wydaje się blokować, jeśli nie ma dopasowania N-tego. Musiałem ograniczyć wartość rozdzielaną przecinkami do 1000 wartości, a to zawieszało się, gdy csv miało mniej. Więc @Yogesh - prawdopodobnie nie jest to dobra akceptowana odpowiedź, jaka jest. ;) Za odmianę tej odpowiedzi (jest ciągiem do wersji strun tutaj ) i zmienił pętli do przystanku przy n-count zamiast.
ruffin
Próbując wyszukać \, przekazana wartość to "\\", a ciąg dopasowania wygląda następująco przed funkcją regex.match: ((). *?) {2}. Pojawia się ten błąd: analizowanie „((). *?) {2}” - za mało). Jaki jest prawidłowy format wyszukiwania ukośników bez błędu?
RichieMN,
3
Przepraszam, ale drobna krytyka: rozwiązania regex są nieoptymalne, ponieważ wtedy muszę ponownie nauczyć się regexów po raz n-ty. Kod jest zasadniczo trudniejszy do odczytania, gdy używane są wyrażenia regularne.
Mark Rogers
19

To w zasadzie to, co musisz zrobić - a przynajmniej jest to najłatwiejsze rozwiązanie. Jedyne, co byś „marnował”, to koszt n wywołań metod - jeśli się nad tym zastanowisz, nie będziesz sprawdzać żadnego przypadku dwa razy. (IndexOf powróci, gdy tylko znajdzie dopasowanie, a ty będziesz kontynuować od miejsca, w którym zostało przerwane).

Oto rekurencyjna implementacja (powyższego pomysłu ) jako metoda rozszerzająca, naśladująca format metody (metod) frameworka:

public static int IndexOfNth(this string input,
                             string value, int startIndex, int nth)
{
    if (nth < 1)
        throw new NotSupportedException("Param 'nth' must be greater than 0!");
    if (nth == 1)
        return input.IndexOf(value, startIndex);
    var idx = input.IndexOf(value, startIndex);
    if (idx == -1)
        return -1;
    return input.IndexOfNth(value, idx + 1, --nth);
}

Oto kilka testów jednostkowych (MBUnit), które mogą Ci pomóc (udowodnić, że są poprawne):

using System;
using MbUnit.Framework;

namespace IndexOfNthTest
{
    [TestFixture]
    public class Tests
    {
        //has 4 instances of the 
        private const string Input = "TestTest";
        private const string Token = "Test";

        /* Test for 0th index */

        [Test]
        public void TestZero()
        {
            Assert.Throws<NotSupportedException>(
                () => Input.IndexOfNth(Token, 0, 0));
        }

        /* Test the two standard cases (1st and 2nd) */

        [Test]
        public void TestFirst()
        {
            Assert.AreEqual(0, Input.IndexOfNth("Test", 0, 1));
        }

        [Test]
        public void TestSecond()
        {
            Assert.AreEqual(4, Input.IndexOfNth("Test", 0, 2));
        }

        /* Test the 'out of bounds' case */

        [Test]
        public void TestThird()
        {
            Assert.AreEqual(-1, Input.IndexOfNth("Test", 0, 3));
        }

        /* Test the offset case (in and out of bounds) */

        [Test]
        public void TestFirstWithOneOffset()
        {
            Assert.AreEqual(4, Input.IndexOfNth("Test", 4, 1));
        }

        [Test]
        public void TestFirstWithTwoOffsets()
        {
            Assert.AreEqual(-1, Input.IndexOfNth("Test", 8, 1));
        }
    }
}
Tod Thomson
źródło
Zaktualizowałem moje formatowanie i przypadki testowe w oparciu o świetne opinie Weston (dzięki Weston).
Tod Thomson
14
private int IndexOfOccurence(string s, string match, int occurence)
{
    int i = 1;
    int index = 0;

    while (i <= occurence && (index = s.IndexOf(match, index + 1)) != -1)
    {
        if (i == occurence)
            return index;

        i++;
    }

    return -1;
}

lub w C # z metodami rozszerzającymi

public static int IndexOfOccurence(this string s, string match, int occurence)
{
    int i = 1;
    int index = 0;

    while (i <= occurence && (index = s.IndexOf(match, index + 1)) != -1)
    {
        if (i == occurence)
            return index;

        i++;
    }

    return -1;
}
Schotime
źródło
5
Jeśli się nie mylę, ta metoda nie powiedzie się, jeśli ciąg do dopasowania zaczyna się na pozycji 0, co można poprawić, ustawiając indexpoczątkowo wartość -1.
Peter Majeed
1
Możesz również chcieć sprawdzić puste lub puste ciągi i dopasować, albo zostanie rzucone, ale to jest decyzja projektowa.
Dzięki @PeterMajeed - jeśli "BOB".IndexOf("B")zwraca 0, więc ta funkcja powinnaIndexOfOccurence("BOB", "B", 1)
PeterX
2
Twoje jest prawdopodobnie najlepszym rozwiązaniem, ponieważ ma zarówno funkcję rozszerzającą, jak i unika wyrażeń regularnych i rekursji, co sprawia, że ​​kod jest mniej czytelny.
Mark Rogers
@tdyen Rzeczywiście, Code Analysis wyda „CA1062: Validate arguments of public methods”, jeśli IndexOfOccurencenie sprawdza, czy sjest null. I String.IndexOf (String, Int32) zgłosi, ArgumentNullExceptionjeśli matchjest null.
DavidRR
1

Może fajnie byłoby też popracować z String.Split()Metodą i sprawdzić, czy żądane wystąpienie znajduje się w tablicy, jeśli nie potrzebujesz indeksu, ale wartość w indeksie

user3227623
źródło
1

Po przeprowadzeniu testów porównawczych wydaje się, że jest to najprostsze i najbardziej wydajne rozwiązanie

public static int IndexOfNthSB(string input,
             char value, int startIndex, int nth)
        {
            if (nth < 1)
                throw new NotSupportedException("Param 'nth' must be greater than 0!");
            var nResult = 0;
            for (int i = startIndex; i < input.Length; i++)
            {
                if (input[i] == value)
                    nResult++;
                if (nResult == nth)
                    return i;
            }
            return -1;
        }
ShadowBeast
źródło
1

System.ValueTuple ftw:

var index = line.Select((x, i) => (x, i)).Where(x => x.Item1 == '"').ElementAt(5).Item2;

napisanie funkcji z tego to praca domowa

Matthias
źródło
0

Odpowiedź Toda można nieco uprościć.

using System;

static class MainClass {
    private static int IndexOfNth(this string target, string substring,
                                       int seqNr, int startIdx = 0)
    {
        if (seqNr < 1)
        {
            throw new IndexOutOfRangeException("Parameter 'nth' must be greater than 0.");
        }

        var idx = target.IndexOf(substring, startIdx);

        if (idx < 0 || seqNr == 1) { return idx; }

        return target.IndexOfNth(substring, --seqNr, ++idx); // skip
    }

    static void Main () {
        Console.WriteLine ("abcbcbcd".IndexOfNth("bc", 1));
        Console.WriteLine ("abcbcbcd".IndexOfNth("bc", 2));
        Console.WriteLine ("abcbcbcd".IndexOfNth("bc", 3));
        Console.WriteLine ("abcbcbcd".IndexOfNth("bc", 4));
    }
}

Wynik

1
3
5
-1
seron
źródło
0

Lub coś takiego z pętlą do while

 private static int OrdinalIndexOf(string str, string substr, int n)
    {
        int pos = -1;
        do
        {
            pos = str.IndexOf(substr, pos + 1);
        } while (n-- > 0 && pos != -1);
        return pos;
    }
xFreeD
źródło
-4

Może to zrobić:

Console.WriteLine(str.IndexOf((@"\")+2)+1);
Sameer Shaikh
źródło
2
Nie wiem, jak to by zadziałało. Czy mógłbyś dołączyć krótkie wyjaśnienie, co to robi?
Bob Kaufman