Den Index des n-ten Vorkommens einer Zeichenfolge abrufen?

100

Was ist der schnellste Weg, um das n- te Vorkommen einer Zeichenfolge innerhalb einer Zeichenfolge zu ermitteln, es sei denn, mir fehlt eine offensichtliche integrierte Methode ?

Mir ist klar, dass ich die IndexOf- Methode schleifen kann , indem ich ihren Startindex bei jeder Iteration der Schleife aktualisiere. Aber es so zu machen, scheint mir verschwenderisch.

PeteT
quelle
Ich würde dafür reguläre Ausdrücke verwenden, dann muss man die Zeichenfolge innerhalb der Zeichenfolge optimal abgleichen. Dies in einem der schönen DSLs, die wir alle verwenden sollten, wenn möglich. Ein Beispiel in VB.net ist der Code in C # fast der gleiche.
Bovium
2
Ich würde gutes Geld in die Version mit regulären Ausdrücken stecken, die wesentlich schwieriger zu finden ist als "weiter schleifen und einfache String.IndexOf machen". Reguläre Ausdrücke haben ihren Platz, sollten aber nicht verwendet werden, wenn einfachere Alternativen existieren.
Jon Skeet

Antworten:

52

Das ist im Grunde das, was Sie tun müssen - oder zumindest die einfachste Lösung. Alles, was Sie "verschwenden" würden, sind die Kosten für n Methodenaufrufe - Sie werden keinen Fall zweimal überprüfen, wenn Sie darüber nachdenken. (IndexOf kehrt zurück, sobald die Übereinstimmung gefunden wurde, und Sie werden dort weitermachen, wo es aufgehört hat.)

Jon Skeet
quelle
2
Ich nehme an, Sie haben Recht, es scheint jedoch, dass es eine eingebaute Methode geben sollte. Ich bin sicher, dass es sich um ein häufiges Ereignis handelt.
PeteT
4
"Ja wirklich?" Ich kann mich nicht erinnern, dass ich es in ungefähr 13 Jahren Java- und C # -Entwicklung jemals tun musste. Das heißt nicht, dass ich es wirklich nie tun musste - aber nur nicht oft genug, um mich zu erinnern.
Jon Skeet
Apropos Java, wir haben StringUtils.ordinalIndexOf(). C # mit all dem Linq und anderen wunderbaren Funktionen hat einfach keine eingebaute Unterstützung dafür. Und ja, es ist sehr wichtig, Unterstützung zu haben, wenn Sie mit Parsern und Tokenizern zu tun haben.
Annie
3
@Annie: Du sagst "wir haben" - meinst du in Apache Commons? In diesem Fall können Sie Ihre eigene Drittanbieter-Bibliothek für .NET genauso einfach schreiben wie für Java. Es ist also nicht so, dass die Java-Standardbibliothek dies mit .NET nicht tut. Und natürlich können Sie es in C # als Erweiterungsmethode hinzufügen string:)
Jon Skeet
108

Sie könnten den regulären Ausdruck wirklich verwenden /((s).*?){n}/, um nach dem n-ten Auftreten von Teilzeichenfolgen zu suchen s.

In C # könnte es so aussehen:

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;
    }
}

Hinweis: Ich habe Regex.Escapedie ursprüngliche Lösung hinzugefügt , um die Suche nach Zeichen zu ermöglichen, die für die Regex-Engine eine besondere Bedeutung haben.

Alexander Prokofyev
quelle
2
solltest du dem entkommen value? In meinem Fall suchte ich nach einem Punkt msdn.microsoft.com/en-us/library/…
russau
3
Dieser Regex funktioniert nicht, wenn die Zielzeichenfolge Zeilenumbrüche enthält. Könnten Sie es beheben? Vielen Dank.
Ignacio Soler Garcia
Scheint zu sperren, wenn es keine N-te Übereinstimmung gibt. Ich musste einen durch Kommas getrennten Wert auf 1000 Werte beschränken, und dies hing, wenn die CSV weniger hatte. Also @Yogesh - wahrscheinlich keine gute akzeptierte Antwort wie sie ist. ;) Eine Variante der Verwendung dieser Antwort (es gibt ein String String - Version hier ) und veränderte die Schleife zu Stopp bei n - te Zählung statt.
Ruffin
Beim Versuch, nach \ zu suchen, lautet der übergebene Wert "\\", und die Übereinstimmungszeichenfolge sieht vor der Funktion regex.match folgendermaßen aus: ((). *?) {2}. Ich erhalte folgende Fehlermeldung: Analyse von "((). *?) {2}" - Nicht genug). Was ist das richtige Format, um fehlerfrei nach Schrägstrichen zu suchen?
RichieMN
3
Entschuldigung, aber ein kleiner Kritikpunkt: Regex-Lösungen sind suboptimal, weil ich dann zum n-ten Mal Regex neu lernen muss. Der Code ist wesentlich schwieriger zu lesen, wenn reguläre Ausdrücke verwendet werden.
Mark Rogers
19

Das ist im Grunde das, was Sie tun müssen - oder zumindest die einfachste Lösung. Alles, was Sie "verschwenden" würden, sind die Kosten für n Methodenaufrufe - Sie werden keinen Fall zweimal überprüfen, wenn Sie darüber nachdenken. (IndexOf kehrt zurück, sobald die Übereinstimmung gefunden wurde, und Sie werden dort weitermachen, wo es aufgehört hat.)

Hier ist die rekursive Implementierung (der obigen Idee ) als Erweiterungsmethode, die das Format der Framework-Methode (n) nachahmt:

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);
}

Außerdem sind hier einige (MBUnit) Unit-Tests aufgeführt, die Ihnen helfen könnten (um zu beweisen, dass sie korrekt sind):

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
quelle
Ich habe meine Formatierungs- und Testfälle basierend auf Westons großartigem Feedback aktualisiert (danke 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;
}

oder in C # mit Erweiterungsmethoden

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
quelle
5
Wenn ich mich nicht irre, schlägt diese Methode fehl, wenn die übereinstimmende Zeichenfolge an Position 0 beginnt. Dies kann korrigiert werden, indem indexzunächst -1 festgelegt wird.
Peter Majeed
1
Möglicherweise möchten Sie auch nach null oder leeren Zeichenfolgen suchen und übereinstimmen, da sonst eine Entwurfsentscheidung getroffen wird.
Danke @PeterMajeed - wenn "BOB".IndexOf("B")0 zurückgegeben wird, sollte diese Funktion auch fürIndexOfOccurence("BOB", "B", 1)
PeterX
2
Ihre ist wahrscheinlich die ultimative Lösung, da sie sowohl eine Erweiterungsfunktion hat als auch Regexs und Rekursionen vermeidet, die beide den Code weniger lesbar machen.
Mark Rogers
@tdyen In der Tat gibt Code Analysis "CA1062: Argumente öffentlicher Methoden validieren" aus, wenn IndexOfOccurencenicht überprüft swird, ob dies der Fall ist null. Und String.IndexOf (String, Int32) werfen wird , ArgumentNullExceptionwenn matchist null.
DavidRR
1

Vielleicht wäre es auch schön, mit der String.Split()Methode zu arbeiten und zu überprüfen, ob sich das angeforderte Vorkommen im Array befindet, wenn Sie nicht den Index, sondern den Wert am Index benötigen

user3227623
quelle
1

Nach einigem Benchmarking scheint dies die einfachste und effizienteste Lösung zu sein

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
quelle
1

System.ValueTuple ftw:

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

eine Funktion daraus zu schreiben ist Hausaufgabe

Matthias
quelle
0

Tods Antwort kann etwas vereinfacht werden.

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));
    }
}

Ausgabe

1
3
5
-1
Seron
quelle
0

Oder so ähnlich mit der do while-Schleife

 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
quelle
-4

Dies könnte es tun:

Console.WriteLine(str.IndexOf((@"\")+2)+1);
Sameer Shaikh
quelle
2
Ich sehe nicht, wie das funktionieren würde. Können Sie kurz erläutern, was dies bewirkt?
Bob Kaufman